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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Balanced Connected Subgraph Problem in Geometric Intersection Graphs 1

引用

13th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2019

作者： Bhore, Sujoy Jana, Satyabrata Pandit, Supantha Roy, Sasanka Algorithms and Complexity Group TU Wien Vienna Austria Indian Statistical Institute Kolkata India Dhirubhai Ambani Institute of Information and Communication Technology GandhinagarGujarat India

ISBN: (数字)9783030364120

ISBN: (纸本)9783030364113

We study the (shortly,) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given agraph, where each vertex in V is colored with either "" or "", the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is, i.e., H contains an equal number of red and blue vertices. We study the computational complexity landscape of the BCS problem while considering geometric intersection graphs. On one hand, we prove that the BCS problem is NP-hard on the unit disk, outer-string, complete grid, and unit square graphs. On the other hand, we design polynomial-time algorithms for the BCS problem on interval, circular-arc and permutation graphs. In particular, we give algorithms for theproblem on both interval and circular-arc graphs, and those algorithms are used as subroutines for solving the BCS problem on the same classes of graphs. Finally, we present a FPT algorithm for the BCS problem on general graphs. © 2019, Springer Nature Switzerland AG.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Unit Disk Representations of Embedded Trees, Outerplanar and Multi-legged Graphs 29th

Unit Disk Representations of Embedded Trees, Outerplanar an...

引用

29th International Symposium on Graph Drawing and Network Visualization, GD 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 Utrecht Netherlands Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

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, Springer Nature Switzerland AG.

关键词： Trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

New complexity-theoretic frontiers of tractability for neural network training 23

New complexity-theoretic frontiers of tractability for neura...

引用

Proceedings of the 37th International Conference on Neural Information Processing Systems

作者： Cornelius Brand Robert Ganian Mathis Rocton Algorithms & Complexity Group Vienna University of Technology Vienna Austria

In spite of the fundamental role of neural networks in contemporary machine learning research, our understanding of the computational complexity of optimally training neural networks remains incomplete even when dealing with the simplest kinds of activation functions. Indeed, while there has been a number of very recent results that establish ever-tighter lower bounds for the problem under linear and ReLU activation functions, less progress has been made towards the identification of novel polynomial-time tractable network architectures. In this article we obtain novel algorithmic upper bounds for training linear- and ReLU-activated neural networks to optimality which push the boundaries of tractability for these problems beyond the previous state of the art. In particular, for ReLU networks we establish the polynomial-time tractability of all architectures where hidden neurons have an out-degree of 1, improving upon the previous algorithm of Arora, Basu, Mianjy and Mukherjee. On the other hand, for networks with linear activation functions we identify the first non-trivial polynomial-time solvable class of networks by obtaining an algorithm that can optimally train network architectures satisfying a novel data throughput condition.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：