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

Parameterized algorithms for Queue Layouts 28th

学校读者我要写书评

暂无评论

Parameterized Algorithms for Queue Layouts

28th International Symposium on Graph Drawing and Network Visualization, GD 2020

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria Bruxelles Belgium Dipartimento di Ingegneria Università degli Studi di Perugia Perugia Italy

ISBN: (纸本)9783030687656

An h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h. © 2020, Springer Nature Switzerland AG.

关键词： Parameter estimation

Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Brand, Cornelius Ceylan, Esra Ganian, Robert Hatschka, Christian Korchemna, Viktoriia Algorithms and Complexity Group TU Wien Vienna Austria

Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of treewidth that is based on edge cuts instead of vertex separators. While tree-cut width has been coined as such an analogue of treewidth for edge cuts, its algorithmic applications have often led to disappointing results: out of twelve problems where one would hope for fixed-parameter tractability parameterized by an edge-cut based analogue to treewidth, eight were shown to be W[1]-hard parameterized by tree-cut width. As our main contribution, we develop an edge-cut based analogue to treewidth called edge-cut width. Edge-cut width is, intuitively, based on measuring the density of cycles passing through a spanning tree of the graph. Its benefits include not only a comparatively simple definition, but mainly that it has interesting algorithmic properties: it can be computed by a fixed-parameter algorithm, and it yields fixed-parameter algorithms for all the aforementioned problems where tree-cut width failed to do so. © 2022, CC BY.

关键词： Parameterization

Small resolution proofs for QBF using dependency treewidth

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Eiben, Eduard Ganian, Robert Ordyniak, Sebastian Algorithms and Complexity Group TU Wien Vienna Austria

In spite of the close connection between the evaluation of quantified Boolean formulas (QBF) and propositional satisfiability (SAT), tools and techniques which exploit structural properties of SAT instances are known to fail for QBF. This is especially true for the structural parameter treewidth, which has allowed the design of successful algorithms for SAT but cannot be straightforwardly applied to QBF since it does not take into account the interdependencies between quantified variables. In this work we introduce and develop dependency treewidth, a new structural parameter based on treewidth which allows the efficient solution of QBF instances. Dependency treewidth pushes the frontiers of tractability for QBF by overcoming the limitations of previously introduced variants of treewidth for QBF. We augment our results by developing algorithms for computing the decompositions that are required to use the parameter. Copyright © 2017, The Authors. All rights reserved.

关键词： Parameter estimation

On Erdős–Szekeres-Type Problems for k-convex Point Sets 1

学校读者我要写书评

暂无评论

30th International Workshop on Combinatorial algorithms, IWOCA 2019

作者： Balko, Martin Bhore, Sujoy Martínez Sandoval, Leonardo Valtr, Pavel Department of Applied Mathematics Charles University Prague Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria Sorbonne Université Paris France

ISBN: (数字)9783030250058

ISBN: (纸本)9783030250041

We study Erdős–Szekeres-type problems for k-convex point sets, a recently introduced notion that naturally extends the concept of convex position. A finite set S of n points is k-convex if there exists a spanning simple polygonization of S such that the intersection of any straight line with its interior consists of at most k connected components. We address several open problems about k-convex point sets. In particular, we extend the well-known Erdős–Szekeres Theorem by showing that, for every fixed k ∈ N, every set of n points in the plane in general position (with no three collinear points) contains a k-convex subset of size at least Ω(logk n). We also show that there are arbitrarily large 3-convex sets of n points in the plane in general position whose largest 1-convex subset has size O(log n). This gives a solution to a problem posed by Aichholzer et al.Â [2]. We prove that there is a constant c > 0 such that, for every n ∈ N, there is a set S of n points in the plane in general position such that every 2-convex polygon spanned by at least c · log n points from S contains a point of S in its interior. This matches an earlier upper bound by Aichholzer et al.Â [2] upÂ to a multiplicative constant and answers another of their open problems. © 2019, Springer Nature Switzerland AG.

关键词： Geometry

LACON-, SHRUB- AND PARITY-DECOMPOSITIONS: CHARACTERIZING TRANSDUCTIONS OF BOUNDED EXPANSION CLASSES

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Dreier, Jan Algorithms and Complexity Group TU Wien Austria

The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in first-order logic can be solved in linear time on bounded expansion graph classes. First-order interpretations and transductions of sparse graph classes lead to more general, dense graph classes that seem to inherit many of the nice algorithmic properties of their sparse counterparts. In this paper, we show that one can encode graphs from a class with structurally bounded expansion via lacon-, shrub- and parity-decompositions from a class with bounded expansion. These decompositions are useful for lifting properties from sparse to structurally sparse graph classes. © 2021, CC BY.

关键词： Expansion

Independent sets of dynamic rectangles: algorithms and experiments

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

We study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on dynamic sets of O(n) axis-parallel rectangles, which can be modeled as dynamic rectangle intersection graphs. We consider the fully dynamic vertex update (insertion/deletion) model for two types of rectangles: (i) uniform height and width and (ii) uniform height and arbitrary width. These types of dynamic vertex update problems arise, e.g., in interactive map labeling. We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of O(Δ) update time (where Δ is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with O(1) update time. In a subsequent algorithm, we establish the trade-off between approximation quality 2(1 + 1/k) and update time O(k2log n) for k ∈ . We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of uniform height and arbitrary width rectangles with O(ω log n) update time, where ω is the largest number of maximal cliques stabbed by any axis-parallel line. We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution size and update time for synthetic and real-world map labeling data sets. Copyright © 2020, The Authors. All rights reserved.

关键词： Geometry

The Power of Collaboration: Learning Large Bayesian Networks at Scale

学校读者我要写书评

暂无评论

The Power of Collaboration: Learning Large Bayesian Networks...

International Conference on Tools for Artificial Intelligence (ICTAI)

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

ISBN: (数字)9798331527235

ISBN: (纸本)9798331527242

We present a novel approach to learn the structure of large Bayesian Networks (BNs) of bounded treewidth. Our approach combines the complementary strengths of heuristic and MaxSAT-based methods. Both methods operate in parallel and cooperate in a mutually advantageous way to improve the quality of the learned BN structures. Our work utilizes an approach proposed by Peruvemba Ramaswamy and Szeider (AAAI'21, NeurIPS'21, UAI'22), which continually applies a MaxSAT-based algorithm to a BN obtained from heuristic search. We create a continuous and dynamic refinement process by allowing the heuristic and the MaxSAT-based technique to cooperate and repeatedly share their work. Our rigorous experiments show that the collaboration between the two methods is a powerful strategy for increasing the score of the learned BN structure. Moreover, the rate at which the score increases is significantly higher than that of the individual methods by themselves. Our results provide a strong argument for combining complementary approaches to learn treewidth-bounded BNs in a collaborative way.

关键词： Image color analysis Heuristic algorithms Collaboration Real-time systems Bayes methods Relays Artificial intelligence Tuning Optimization Bars

The Parameterized complexity Landscape of the Unsplittable Flow Problem

学校读者我要写书评

暂无评论

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.

关键词：

PACE Solver Description: Touiouidth 18

学校读者我要写书评

暂无评论

PACE Solver Description: Touiouidth

18th International Symposium on Parameterized and Exact Computation, IPEC 2023

作者： Berthe, Gaétan Coudert-Osmont, Yoann Dobler, Alexander Morelle, Laure Reinald, Amadeus Rocton, Mathis LIRMM CNRS Université de Montpellier France Université de Lorraine CNRS Inria LORIA France Algorithms and Complexity Group TU Wien Austria

We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++... 详细信息

ISBN: (纸本)9783959773058

关键词： Branch and bound method