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

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

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity of Coordinated Motion Planning 39

The Parameterized Complexity of Coordinated Motion Planning

引用

39th International Symposium on Computational Geometry, SoCG 2023

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University ChicagoIL United States

ISBN: (纸本)9783959772730

In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n2 − 1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids. © Eduard Eiben, Robert Ganian, and Iyad Kanj;licensed under Creative Commons License CC-BY 4.0.

关键词： Motion planning

来源：评论

学校读者我要写书评

暂无评论

Coloring random graphs online without creating monochromatic subgraphs

Coloring random graphs online without creating monochromatic...

引用

作者： Mütze, Torsten Rast, Thomas Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

ISBN: (纸本)9780898719932

Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph Gn,p on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of Gn,p are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of r available colors. It is known that for any fixed graph F and any fixed integer r ≥ 2 this problem has a threshold p0(F,r,n) in the following sense: For any function p(n) = o(p0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of Gn,p that is valid w.r.t. F online, and for any function p(n) = ω(p0) any online strategy will a.a.s. fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic two-player game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a value γ = γ(F,r) such that the threshold of the probabilistic problem is given by p0(F,r,n) = nγ. Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of Gn,p online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n-γ).

关键词： Coloring

来源：评论

学校读者我要写书评

暂无评论

The k-Opt Algorithm for the Traveling Salesman Problem Has Exponential Running Time for k ≥ 5 51

The k-Opt Algorithm for the Traveling Salesman Problem Has E...

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Heimann, Sophia Hoang, Hung P. Hougardy, Stefan Research Institute for Discrete Mathematics University of Bonn Germany Algorithms and Complexity Group Faculty of Informatics TU Wien Austria Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics University of Bonn Germany

ISBN: (纸本)9783959773225

The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the k-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the k-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires k 1000 and has a substantial gap. We show the two properties above for a much smaller value of k, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for k ≥ 17 and the exponential running time for k ≥ 5. © Sophia Heimann, Hung P. Hoang, and Stefan Hougardy.

关键词： Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

On the Upward Book Thickness Problem: Combinatorial and complexity Results 29th

On the Upward Book Thickness Problem: Combinatorial and Com...

引用

29th International Symposium on Graph Drawing and Network Visualization, GD 2021

作者： Bhore, Sujoy Da Lozzo, Giordano Montecchiani, Fabrizio Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Roma Tre University Rome Italy Department of Engineering University of Perugia Perugia Italy Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are st-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP-hard for any fixed k≥ 3. We show that the problem, for any k≥ 5, remains NP-hard for graphs whose domination number is O(k), but it is FPT in the vertex cover number. © 2021, Springer Nature Switzerland AG.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity of Network Microaggregation 37

The Parameterized Complexity of Network Microaggregation

引用

37th AAAI Conference on Artificial Intelligence, AAAI 2023

作者： Blažej, Václav Ganian, Robert Knop, Dušan Pokorný, Jan Schierreich, Šimon Simonov, Kirill Faculty of Information Technology Czech Technical University in Prague Prague Czech Republic Algorithms and Complexity Group Technische Universität Wien Vienna Austria Hasso Plattner Institute University of Potsdam Postdam Germany

ISBN: (纸本)9781577358800

Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network. Copyright © 2023, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Constrained Boundary Labeling

arXiv

引用

arXiv 2024年

作者： Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Algorithms and Complexity Group TU Wien Austria Algorithms cluster TU Eindhoven Netherlands Technical University of Munich Germany

Boundary labeling is a technique in computational geometry used to label dense sets of feature points in an illustration. It involves placing labels along an axis-aligned bounding box and connecting each label with its corresponding feature point using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Finally, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. © 2024, CC BY.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: Treewidth modulator: Emergency exit for DFVS 45

Brief announcement: Treewidth modulator: Emergency exit for ...

引用

45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

作者： Lokshtanov, Daniel Ramanujan, M.S. Saurabh, Saket Sharma, Roohani Zehavi, Meirav Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences HBNI UMI ReLax India Department of Computer Science Ben-Gurion University Israel

ISBN: (纸本)9783959770767

In the Directed Feedback Vertex Set (DFVS) problem, we are given as input a directed graph D and an integer k, and the objective is to check whether there exists a set S of at most k vertices such that F = D − S is a directed acyclic graph (DAG). Determining whether DFVS admits a polynomial kernel (parameterized by the solution size) is one of the most important open problems in parameterized complexity. In this article, we give a polynomial kernel for DFVS parameterized by the solution size plus the size of any treewidth-η modulator, for any positive integer η. We also give a polynomial kernel for the problem, which we call Vertex Deletion to treewidth-η DAG, where given as input a directed graph D and a positive integer k, the objective is to decide whether there exists a set of at most k vertices, say S, such that D − S is a DAG and the treewidth1 of D − S is at most η. © 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

First-order logic in finite domains: Where semantic evaluation competes with SMT solving

arXiv

引用

arXiv 2021年

作者： Schreiner, Wolfgang Reichl, Franz-Xaver Johannes Kepler University Linz Austria Algorithms and Complexity Group Tu Wien Austria

In this paper, we compare two alternative mechanisms for deciding the validity of first-order formulas over finite domains supported by the mathematical model checker RISCAL: first, the original approach of "semantic evaluation" (based on an implementation of the denotational semantics of the RISCAL language) and, second, the later approach of SMT solving (based on satisfiability preserving translations of RISCAL formulas to SMT-LIB formulas as inputs for SMT solvers). After a short presentation of the two approaches and a discussion of their fundamental pros and cons, we quantitatively evaluate them, both by a set of artificial benchmarks and by a set of benchmarks taken from real-life applications of RISCAL;for this, we apply the state-of-the-art SMT solvers Boolector, CVC4, Yices, and Z3. Our benchmarks demonstrate that (while SMT solving generally vastly outperforms semantic evaluation), the various SMT solvers exhibit great performance differences. More important, we identify classes of formulas where semantic evaluation is able to compete with (or even outperform) satisfiability solving, outlining some room for improvements in the translation of RISCAL formulas to SMT-LIB formulas as well as in the current SMT technology. © 2021, CC BY.

关键词： Benchmarking

来源：评论

学校读者我要写书评

暂无评论

The complexity landscape of decompositional parameters for ILP

arXiv

引用

arXiv 2018年

作者： Ganian, Robert Ordyniak, Sebastian Algorithms and Complexity Group TU Wien Favoritenstrasse 9-11 Wien1040 Austria

Integer Linear Programming (ILP) can be seen as the archetypical problem for NP-complete optimization problems, and a wide range of problems in artificial intelligence are solved in practice via a translation to ILP. Despite its huge range of applications, only few tractable fragments of ILP are known, probably the most prominent of which is based on the notion of total unimodularity. Using entirely different techniques, we identify new tractable fragments of ILP by studying structural parameterizations of the constraint matrix within the framework of parameterized complexity. In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we give an overview of the complexity of ILP w.r.t. decompositional parameters defined on the constraint matrix. Copyright © 2018, The Authors. All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：