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

arXiv 2019年

作者： Ganian, Robert Lodha, Neha Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria Algorithms Group University of Sheffield Sheffield United Kingdom

The decomposition of graphs is a prominent algorithmic task with numerous applications in computer science. A graph decomposition method is typically associated with a width parameter (such as treewidth) that indicates how well the given graph can be decomposed. Many hard (even #P-hard) algorithmic problems can be solved efficiently if a decomposition of small width is provided;the runtime, however, typically depends exponentially on the decomposition width. Finding an optimal decomposition is itself an NP-hard task. In this paper we propose, implement, and test the first practical decomposition algorithms for the width parameters treecut width and treedepth. These two parameters have recently gained a lot of attention in the theoretical research community as they offer the algorithmic advantage over treewidth by supporting so-called fixed-parameter algorithms for certain problems that are not fixed-parameter tractable with respect to treewidth. However, the existing research has mostly been theoretical. A main obstacle for any practical or experimental use of these two width parameters is the lack of any practical or implemented algorithm for actually computing the associated decompositions. We address this obstacle by providing the first practical decomposition algorithms. Our approach for computing treecut width and treedepth decompositions is based on efficient encodings of these decomposition methods to the propositional satisfiability problem (SAT). Once an encoding is generated, any satisfiability solver can be used to find the decomposition. This allows us to leverage the surprising power of todays state-of-the art SAT solvers. The success of SAT-based decomposition methods crucially depends on the used characterisation of the decomposition method, as not every characterisation is suitable for that task. For instance, the successful leading SAT encoding for treewidth is based on a characterisation of treewidth in terms of elimination orderings. For treecut w

关键词： Signal encoding

来源：评论

学校读者我要写书评

暂无评论

Multiplicative approximations and the hypervolume indicator

Multiplicative approximations and the hypervolume indicator

引用

11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009

作者： Friedrich, Tobias Horoba, Christian Neumann, Frank Algorithms Group International Computer Science Institute Berkeley CA United States Fakultät für Informatik LS 2 Technische Universität Dortmund Dortmund Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarbrücken Germany

ISBN: (纸本)9781605583259

Indicator-based algorithms have become a very popular approach to solve multi-objective optimization problems. In this paper, we contribute to the theoretical understanding of algorithms maximizing the hypervolume for a given problem by distributing μ points on the Pareto front. We examine this common approach with respect to the achieved multiplicative approximation ratio for a given multi-objective problem and relate it to a set of μ points on the Pareto front that achieves the best possible approximation ratio. For the class of linear fronts and a class of concave fronts, we prove that the hypervolume gives the best possible approximation ratio. In addition, we examine Pareto fronts of different shapes by numerical calculations and show that the approximation computed by the hypervolume may differ from the optimal approximation ratio. Copyright 2009 ACM.

关键词： Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

The power of cut-based parameters for computing edge disjoint paths

arXiv

引用

arXiv 2018年

作者： Ganian, Robert Ordyniak, Sebastian Algorithms and Complexity group TU Wien Vienna Austria Algorithms group University of Sheffield Sheffield United Kingdom

This paper revisits the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in P in any way. In this setting, EDP is known to remain NP-hard even on extremely restricted graph classes, such as graphs with a vertex cover of size 3. We present three results which use edge-separator based parameters to chart new islands of tractability in the complexity landscape of EDP. Our first and main result utilizes the fairly recent structural parameter treecut width (a parameter with fundamental ties to graph immersions and graph cuts): we obtain a polynomial-time algorithm for EDP on every graph class of bounded treecut width. Our second result shows that EDP parameterized by treecut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph. Copyright © 2018, The Authors. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

Hedonic Diversity Games: A complexity Picture with More than Two Colors

arXiv

引用

arXiv 2022年

作者： Ganian, Robert Hamm, Thekla Knop, Dušan Schierreich, Šimon Suchý, Ondřej Algorithms and Complexity Group TU Wien Austria Algorithms and Complexity Group Utrecht University Netherlands Faculty of Information Technology Czech Technical University Prague Czech Republic

Hedonic diversity games are a variant of the classical hedonic games designed to better model a variety of questions concerning diversity and fairness. Previous works mainly targeted the case with two diversity classes (represented as colors in the model) and provided some initial complexity-theoretic and existential results concerning Nash and individually stable outcomes. Here, we design new algorithms accompanied with lower bounds which provide a comprehensive parameterized-complexity picture for computing Nash and individually stable outcomes with respect to the most natural parameterizations of the problem. Crucially, our results hold for general hedonic diversity games where the number of colors is not necessarily restricted to two, and show that—apart from two trivial cases—a necessary condition for tractability in this setting is that the number of colors is bounded by the parameter. Moreover, for the special case of two colors we resolve an open question asked in previous work (Boehmer and Elkind, AAAI 2020). Copyright © 2022, The Authors. All rights reserved.

关键词： Color

来源：评论

学校读者我要写书评

暂无评论

Compatible Cycle Decomposition of bad K₅-minor-free graphs

引用

Electronic Notes in Discrete Mathematics 2017年 61卷 445-449页

作者： Fleischner, Herbert Bagheri Gh., Behrooz Zhang, Cun-Quan Zhang, Zhang Algorithms and Complexity Group Vienna University of Technology Favoritenstrasse 9-11 Vienna 1040 Austria Department of Mathematics West Virginia University Morgantown 26506-6310 WV United States

Let G be an eulerian graph. For each vertex v∈V(G), let T(v) be a non-empty subset of a partition of the edges incident with v into 2-subsets and set T=∪v∈V(G)T(v), called a transition system of G. A transition sys... 详细信息

Let G be an eulerian graph. For each vertex v∈V(G), let T(v) be a non-empty subset of a partition of the edges incident with v into 2-subsets and set T=∪_v∈V(G)T(v), called a transition system of G. A transition system T of G is admissible if T∩F|≤[Formula presented]|F| for every T∈T and every edge cut F of G. A cycle decomposition C of G is called a compatible cycle decomposition (CCD for short) of (G, T) if |E(C)∩T|≤1 for every cycle C∈C and every T∈T. H. Fleischner proved that if G is planar, then for every admissible transition system T of G, (G, T) has a CCD. G. Fan and C.-Q. Zhang (2000, J. Combin. Theory Ser. B 78, 1-23) showed that this result is also true for K₅-minor-free graphs. We generalize this result to all eulerian graphs that do not contain a special type of K₅-minor which is called a bad K₅-minor. To this purpose, we characterise the 4−regular “hereditary” bad K₅-minor-free graphs (G, T) in which every CCD of (G, T) is a pair of hamiltonian cycles. © 2017 Elsevier B.V.

关键词： Bad K5 Compatible cycle decomposition Transition system

来源：评论

学校读者我要写书评

暂无评论

The complexity of Optimizing Atomic Congestion

arXiv

引用

arXiv 2023年

作者： Brand, Cornelius Ganian, Robert Kalyanasundaram, Subrahmanyam Inerney, Fionn Mc Algorithms & Complexity Theory Group Regensburg University Germany Algorithms and Complexity Group TU Wien Austria Department of Computer Science and Engineering IIT Hyderabad India

Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory, and are capable of modeling congestion and flow optimization tasks in various application areas. While both the price of anarchy for such games as well as the computational complexity of computing their Nash equilibria are by now well-understood, the computational complexity of computing a system-optimal set of strategies—that is, a centrally planned routing that minimizes the average cost of agents—is severely understudied in the literature. We close this gap by identifying the exact boundaries of tractability for the problem through the lens of the parameterized complexity paradigm. After showing that the problem remains highly intractable even on extremely simple networks, we obtain a set of results which demonstrate that the structural parameters which control the computational (in)tractability of the problem are not vertex-separator based in nature (such as, e.g., treewidth), but rather based on edge separators. We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem. Copyright © 2023, The Authors. All rights reserved.

关键词： Separators

来源：评论

学校读者我要写书评

暂无评论

Level Planarity Is More Difficult Than We Thought 32

Level Planarity Is More Difficult Than We Thought

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Fink, Simon D. Pfretzschner, Matthias Rutter, Ignaz Stumpf, Peter Algorithms and Complexity Group Technische Universität Wien Austria Faculty of Computer Science and Mathematics Universität Passau Germany Charles University Prague Czech Republic

We consider three simple quadratic-time algorithms for Level Planarity and give a level-planar instance that they either falsely classify as negative or for which they output a non-planar drawing. © Simon D. Fink... 详细信息

ISBN: (纸本)9783959773430

关键词： Consensus algorithm

来源：评论

学校读者我要写书评

暂无评论

Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized algorithms 47

Long Cycles in Graphs: Extremal Combinatorics Meets Paramete...

引用

47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022

作者： Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Department of Informatics University of Bergen Norway St. Petersburg Department V.A. Steklov Institute of Mathematics Russia Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959772563

We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d > 1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdos-Gallai from 1959, states that a graph G with the average vertex degree D > 1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems, to decide whether a 2-connected graph contains a cycle of length at least 2d + k or of a cycle of length at least D + k, is fixed-parameter tractable parameterized by k. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

A join-based hybrid parameter for constraint satisfaction

arXiv

引用

arXiv 2019年

作者： Ganian, Robert Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria Algorithms Group University of Sheffield Sheffield United Kingdom

We propose joinwidth, a new complexity parameter for the Constraint Satisfaction Problem (CSP). The definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes both the graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances. Copyright © 2019, The Authors. All rights reserved.

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Minimum Link Fencing 33

Minimum Link Fencing

引用

33rd International Symposium on algorithms and Computation, ISAAC 2022

作者： Bhore, Sujoy Klute, Fabian Löffler, Maarten Nöllenburg, Martin Terziadis, Soeren Villedieu, Anaïs Department of Computer Science & Engineering Indian Institute of Technology Bombay India Department of Information and Computing Sciences Utrecht University Netherlands Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772587

We study a variant of the geometric multicut problem, where we are given a set P of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where P contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of P \ {Q} does not intersect Q. © Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：