检索结果-内蒙古大学图书馆

arXiv 2022年

作者： Focke, Jacob Marx, Dániel Mc Inerney, Fionn Neuen, Daniel Sankar, Govind S. Schepper, Philipp Wellnitz, Philip CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria School of Computing Science Simon Fraser University Canada Duke University United States Max Planck Institute for Informatics SIC Germany

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u) ∩S| ∈ σ for every u ∈ S, and |N(v) ∩S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value cσ,ρ such that there is an algorithm that counts (σ, ρ)sets in time ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite;rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining cσ,ρ, we say that (σ, ρ) is m-structured if there is a pair (α, β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • cσ,ρ = stop + rtop + 2 if (σ, ρ) is not m-structured for any m ≥ 2, • cσ,ρ = max{stop, rtop}+ 2 if (σ, ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise, we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the Exact Independent Dominating Set problem (also known as Perfect Code) corresponding to σ = algorithms and ρ = algorithms, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw · nO(1). Despite the unusually delicate definition of cσ,ρ, an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any Ε > 0, a (cσ,ρ−Ε)tw ·nO(1)-algorithm counting the number of (σ, ρ)-sets would violate the C

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution

arXiv

引用

arXiv 2022年

作者： Bekos, Michael A. Gronemann, Martin Montecchiani, Fabrizio Symvonis, Antonios Department of Mathematics University of Ioannina Ioannina Greece Algorithms and Complexity Group TU Wien Vienna Austria Department of Engineering University of Perugia Perugia Italy School of Applied Mathematical & Physical Sciences National Technical University of Athens Athens Greece

We continue the study of the area requirement of convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph editors, we additionally require the obtained drawings to have bounded edge-vertex resolution, that is, the closest distance between a vertex and any non-incident edge is lower bounded by a constant that does not depend on the size of the graph. We present a drawing algorithm that takes as input a 3-connected plane graph with n vertices and f internal faces and computes a convex straight-line drawing with edge-vertex resolution at least 12 on an integer grid of size (n − 2 + a) × (n − 2 + a), where a = min{n − 3, f}. Our result improves the previously best-known area bound of (3n − 7) × (3n − 7)/2 by Chrobak, Goodrich and Tamassia. © 2022, CC0.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Unit disk representations of embedded trees, outerplanar and multi-legged graphs

arXiv

引用

arXiv 2021年

作者： Bhore, Sujoy Löffler, Maarten Nickel, Soeren Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Department of Computing and Information Sciences Utrecht University Algorithms and Complexity Group TU Wien Vienna Austria

A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP-hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that it can be decided in linear time if a lobster graph admits a weak UDC, which permits intersections between disks of non-adjacent vertices. © 2021, CC BY.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

Extending nearly complete 1-planar drawings in polynomial time 45

Extending nearly complete 1-planar drawings in polynomial ti...

引用

45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Klute, Fabian Nöllenburg, Martin Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria Department of Information and Computing Sciences Utrecht University Netherlands

ISBN: (纸本)9783959771597

The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph G, a connected subgraph H of G and a drawing H of H, the extension problem asks whether H can be extended into a drawing of G while maintaining some desired property of the drawing (e.g., planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when H can be obtained from G by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision algorithm. © Nathalie Bertrand;licensed under Creative Commons License CC-BY 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020).

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Detours in Directed Graphs

arXiv

引用

arXiv 2022年

作者： Fomin, Fedor V. Golovach, Petr A. Lochet, William Sagunov, Danil Simonov, Kirill Saurabh, Saket Department of Informatics University of Bergen Norway St. Petersburg Department V.A. Steklov Institute of Mathematics Russia JetBrains Research Saint Petersburg Russia Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences HBNI Chennai India

We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s, t)-path of length at least distG(s, t) + k (where distG(s, t) denotes the length of a shortest path from s to t). Bezáková et al. [7] proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2O(k) · n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2O(k) · nO(1) time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NP-complete even for k = 1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1, . . ., 4} and is NP-complete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem. © 2022, CC BY.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Finding a battleship of uncertain shape

arXiv

引用

arXiv 2022年

作者： Hainzl, Eva-Maria Löffler, Maarten Perz, Daniel Tkadlec, Josef Wallinger, Markus Institute of Discrete Mathematics and Geometry TU Wien Austria Department of Computing and Information Sciences Utrecht University Netherlands Institute of Software Technology TU Graz Austria Department of Mathematics Harvard University United States Algorithms and Complexity Group TU Wien Austria

Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension d ϵ {1, 2}. A ship is a subset of d. Given a family F of ships, we say that an infinite subset X ⊂ dof the cells pierces F, if it intersects each translate of each ship in F (by a vector in d). In this work, we study the lowest possible (asymptotic) density π(F) of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case |F| = 1 (a single ship). As our main contribution, we present a formula for π(F) when F consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding π(F) in 1D. © 2022, CC BY.

关键词： Ships

来源：评论

学校读者我要写书评

暂无评论

Recognizing DAGs with Page-Number 2 is NP-complete

arXiv

引用

arXiv 2022年

作者： Bekos, Michael A. Da Lozzo, Giordano Frati, Fabrizio Gronemann, Martin McHedlidze, Tamara Raftopoulou, Chrysanthi Department of Mathematics University of Ioannina Ioannina Greece Department of Engineering Roma Tre University Italy Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science Utrecht University Utrecht Netherlands School of Applied Mathematical & Physical Sciences NTUA Athens Greece

The page-number of a directed acyclic graph (a DAG, for short) is the minimum k for which the DAG has a topological order and a k-coloring of its edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological order. In 1999, Heath and Pemmaraju conjectured that the recognition of DAGs with page-number 2 is NP-complete and proved that recognizing DAGs with page-number 6 is NP-complete [SIAM J. Computing, 1999]. Binucci et al. recently strengthened this result by proving that recognizing DAGs with page-number k is NP-complete, for every k ≥ 3 [SoCG 2019]. In this paper, we finally resolve Heath and Pemmaraju's conjecture in the affirmative. In particular, our NP-completeness result holds even for st-planar graphs and planar posets. Copyright © 2022, The Authors. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for book embedding problems

引用

Journal of Graph algorithms and Applications 2020年第4期24卷 603-620页

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria Engineering Department University of Perugia Perugia Italy

A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called Fixed-Order Book Thick-ness, or not fixed, called Book Thickness. Both problems are known to be NP-complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order. © 2020, Brown University. All rights reserved.

关键词： Embeddings

来源：评论

学校读者我要写书评

暂无评论

Recognizing Map Graphs of Bounded Treewidth

arXiv

引用

arXiv 2022年

作者： Angelini, Patrizio Bekos, Michael A. Da Lozzo, Giordano Gronemann, Martin Montecchiani, Fabrizio Tappini, Alessandra Department of Mathematics Natural and Applied Sciences John Cabot University Rome Italy Department of Mathematics University of Ioannina Ioannina Greece Department of Engineering Roma Tre University Rome Italy Algorithms and Complexity Group TU Wien Vienna Austria Department of Engineering University of Perugia Perugia Italy

A map graph is a graph admitting a representation in which vertices are nations on a spherical map and edges are shared curve segments or points between nations. We present an explicit fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. The algorithm has time complexity that is linear in the size of the graph and, if the input is a yes-instance, it reports a certificate in the form of a so-called witness. Furthermore, this result is developed within a more general algorithmic framework that allows to test, for any k, if the input graph admits a k-map (where at most k nations meet at a common point) or a hole-free k-map (where each point of the sphere is covered by at least one nation). We point out that, although bounding the treewidth of the input graph also bounds the size of its largest clique, the latter alone does not seem to be a strong enough structural limitation to obtain an efficient time complexity. In fact, while the largest clique in a k-map graph is b3k/2c, the recognition of k-map graphs is still open for any fixed k ≥ 5. Copyright © 2022, The Authors. All rights reserved.

关键词： Machine learning

来源：评论

学校读者我要写书评

暂无评论

Polynomial kernels for edge modification problems towards block and strictly chordal graphs

引用

Discrete Mathematics and Theoretical Computer Science 2025年 272卷

作者： Dumas, Maël Perez, Anthony Rocton, Mathis Todinca, Ioan Institute of Informatics University of Warsaw Warsaw Poland Université d’Orléans INSA CVL LIFO UR 4022 Orléans France Algorithms and Complexity Group TU Wien Vienna Austria

We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph G = (V, E) and an integer k ∈ N and seeks to edit (add or delete) at most k edges from G to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide: © 2025 by the author(s)

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：