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

arXiv 2023年

作者： Dobler, Alexander Algorithms and Complexity Group TU Wien Austria

In 2011, Harrigan and Healy published a polynomial-time algorithm for one-sided crossing minimization for trees [2]. We point out a counterexample to that algorithm, and show that one-sided crossing minimization is NP... 详细信息

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Structure-Guided Local Improvement for Maximum Satisfiability 30

Structure-Guided Local Improvement for Maximum Satisfiabilit...

引用

30th International Conference on Principles and Practice of Constraint Programming, CP 2024

作者： Schidler, André Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773362

The enhanced performance of today's MaxSAT solvers has elevated their appeal for many large-scale applications, notably in software analysis and computer-aided design. Our research delves into refining anytime MaxSAT solving by repeatedly identifying and solving with an exact solver smaller subinstances that are chosen based on the graphical structure of the instance. We investigate various strategies to pinpoint these subinstances. This structure-guided selection of subinstances provides an exact solver with a high potential for improving the current solution. Our exhaustive experimental analyses contrast our methodology as instantiated in our tool MaxSLIM with previous studies and benchmark it against leading-edge MaxSAT solvers. © André Schidler and Stefan Szeider.

关键词： graphical structure incomplete MaxSAT large neighborhood search (LNS) maximum satisfiability metaheuristic SAT-based local improvement (SLIM)

来源：评论

学校读者我要写书评

暂无评论

SAT modulo symmetries for graph generation 27

SAT modulo symmetries for graph generation

引用

27th International Conference on Principles and Practice of Constraint Programming, CP 2021

作者： Kirchweger, Markus Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772112

We propose a novel constraint-based approach to graph generation. Our approach utilizes the interaction between a CDCL SAT solver and a special symmetry propagator where the SAT solver runs on an encoding of the desired graph property. The symmetry propagator checks partially generated graphs for minimality w.r.t. a lexicographic ordering during the solving process. This approach has several advantages over a static symmetry breaking: (i) symmetries are detected early in the generation process, (ii) symmetry breaking is seamlessly integrated into the CDCL procedure, and (iii) the propagator can perform a complete symmetry breaking without causing a prohibitively large initial encoding. We instantiate our approach by generating extremal graphs with certain restrictions in terms of girth and diameter. With our approach, we could confirm the Simon-Murty Conjecture (1979) on diameter-2-critical graphs for graphs up to 18 vertices. © Markus Kirchweger and Stefan Szeider.

关键词： Encoding (symbols)

来源：评论

学校读者我要写书评

暂无评论

A (3/2 + Ε)-Approximation for Multiple TSP with a Variable Number of Depots 31

A (3/2 + Ε)-Approximation for Multiple TSP with a Variable ...

引用

31st Annual European Symposium on algorithms, ESA 2023

作者： Deppert, Max Kaul, Matthias Mnich, Matthias Institute for Algorithms and Complexity Hamburg University of Technology Germany

ISBN: (纸本)9783959772952

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v0, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a (2 − 1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of nΘ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time nΘ(d), which reduces the problem to approximating metric TSP. In this paper we overcome the nΘ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/Ε)O(d log d) · nO(1), and produces a (3/2 + Ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2d · nO(1) © Max Deppert, Matthias Kaul, and Matthias Mnich.

关键词： Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity Landscape of the Unsplittable Flow Problem

arXiv

引用

arXiv 2024年

作者： Ganian, Robert Rocton, Mathis Unterberger, Daniel Algorithms and Complexity Group TU Wien Vienna Austria

We study the well-established problem of finding an optimal routing of unsplittable flows in a graph. While by now there is an extensive body of work targeting the problem on graph classes such as paths and trees, we aim at using the parameterized paradigm to identify its boundaries of tractability on general graphs. We develop novel algorithms and lower bounds which result in a full classification of the parameterized complexity of the problem with respect to natural structural parameterizations for the problem—notably maximum capacity, treewidth, maximum degree, and maximum flow length. In particular, we obtain a fixed-parameter algorithm for the problem when parameterized by all four of these parameters, establish XP-tractability as well as W[1]hardness with respect to the former three and latter three parameters, and all remaining cases remain paraNP-hard. © 2024, CC BY.

关键词：

来源：评论

学校读者我要写书评

暂无评论

A SAT Solver's Opinion on the Erdos-Faber-Lovász Conjecture 26

A SAT Solver's Opinion on the Erdos-Faber-Lovász Conjecture

引用

26th International Conference on Theory and Applications of Satisfiability Testing, SAT 2023

作者： Kirchweger, Markus Peitl, Tomas Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772860

In 1972, Paul Erdos, Vance Faber, and Lászlo Lovász asked whether every linear hypergraph with n vertices can be edge-colored with n colors, a statement that has come to be known as the EFL conjecture. Erdos himself considered the conjecture as one of his three favorite open problems, and offered increasing money prizes for its solution on several occasions. A proof of the conjecture was recently announced, for all but a finite number of hypergraphs. In this paper we look at some of the cases not covered by this proof. We use SAT solvers, and in particular the SAT Modulo Symmetries (SMS) framework, to generate non-colorable linear hypergraphs with a fixed number of vertices and hyperedges modulo isomorphisms. Since hypergraph colorability is NP-hard, we cannot directly express in a propositional formula that we want only non-colorable hypergraphs. Instead, we use one SAT (SMS) solver to generate candidate hypergraphs modulo isomorphisms, and another to reject them by finding a coloring. Each successive candidate is required to defeat all previous colorings, whereby we avoid having to generate and test all linear hypergraphs. Computational methods have previously been used to verify the EFL conjecture for small hypergraphs. We verify and extend these results to larger values and discuss challenges and directions. Ours is the first computational approach to the EFL conjecture that allows producing independently verifiable, DRAT proofs. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

MaxSAT-Based Postprocessing for Treedepth 26th

MaxSAT-Based Postprocessing for Treedepth

引用

26th International Conference on Principles and Practice of Constraint Programming, CP 2020

作者： Peruvemba Ramaswamy, Vaidyanathan Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

Treedepth is an increasingly popular graph invariant. Many NP-hard combinatorial problems can be solved efficiently on graphs of bounded treedepth. Since the exact computation of treedepth is itself NP-hard, recent research has focused on the development of heuristics that compute good upper bounds on the treedepth. In this paper, we introduce a novel MaxSAT-based approach for improving a heuristically obtained treedepth decomposition. At the core of our approach is an efficient MaxSAT encoding of a weighted generalization of treedepth arising naturally due to subtree contractions. The encoding is applied locally to the given treedepth decomposition to reduce its depth, in conjunction with the collapsing of subtrees. We show the local improvement method’s correctness and provide an extensive experimental evaluation with some encouraging results. © 2020, Springer Nature Switzerland AG.

关键词： Forestry

来源：评论

学校读者我要写书评

暂无评论

Mixed Linear Layouts: complexity, Heuristics, and Experiments

arXiv

引用

arXiv 2019年

作者： de Col, Philipp Klute, Fabian Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

A k-page linear graph layout of a graph G = (V, E) draws all vertices along a line and each edge in one of k disjoint halfplanes called pages, which are bounded by . We consider two types of pages. In a stack page no two edges should cross and in a queue page no edge should be nested by another edge. A crossing (nesting) in a stack (queue) page is called a conflict. The algorithmic problem is twofold and requires to compute (i) a vertex ordering and (ii) a page assignment of the edges such that the resulting layout is either conflict-free or conflict-minimal. While linear layouts with only stack or only queue pages are well-studied, mixed s-stack q-queue layouts for s, q ≥ 1 have received less attention. We show NP-completeness results on the recognition problem of certain mixed linear layouts and present a new heuristic for minimizing conflicts. In a computational experiment for the case s, q = 1 we show that the new heuristic is an improvement over previous heuristics for linear layouts. Copyright © 2019, The Authors. All rights reserved.

关键词： Queueing theory

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity of Extending Stack Layouts

arXiv

引用

arXiv 2024年

作者： Depian, Thomas Fink, Simon D. Ganian, Robert Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

An -page stack layout (also known as an -page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into stacks (or pages), such that the endpoints of no two edges on the same stack alternate. We study the problem of extending a given partial -page stack layout into a complete one, which can be seen as a natural generalization of the classical NP-hard problem of computing a stack layout of an input graph from scratch. Given the inherent intractability of the problem, we focus on identifying tractable fragments through the refined lens of parameterized complexity analysis. Our results paint a detailed and surprisingly rich complexitytheoretic landscape of the problem which includes the identification of paraNP-hard, W[1]-hard and XP-tractable, as well as fixed-parameter tractable fragments of stack layout extension via a natural sequence of parameterizations. © 2024, CC BY.

关键词： Graph embeddings

来源：评论

学校读者我要写书评

暂无评论

Minimizing crossings in constrained two-sided circular graph layouts 34

Minimizing crossings in constrained two-sided circular graph...

引用

34th International Symposium on Computational Geometry, SoCG 2018

作者： Klute, Fabian Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959770668

Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal k-plane set of exteriorly drawn edges for k > 1, extending the previously studied case k = 0. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show NP-hardness for arbitrary k, present an efficient algorithm for k = 1, and generalize it to an explicit XP-time algorithm for any fixed k. For the practically interesting case k = 1 we implemented our algorithm and present experimental results that confirm the applicability of our algorithm. © Fabian Klute and Martin Nöllenburg;licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).

关键词： Drawing (graphics)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：