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

On the complexity landscape of connected f-factor problems 41

学校读者我要写书评

暂无评论

On the complexity landscape of connected f-factor problems

41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

作者： Ganian, Robert Narayanaswamy, N.S. Ordyniak, Sebastian Rahul, C.S. Ramanujan, M.S. Algorithms and Complexity Group TU Wien Vienna Austria Indian Institute of Technology Madras Chennai India FI MU Brno Czech Republic

ISBN: (纸本)9783959770163

Given an n-vertex graph G and a function f : V (G) → {0, . . . , n-1}, an f-factor is a subgraph H of G such that degH(v) = f(v) for every vertex v ϵ V (G);we say that H is a connected f-factor if, in addition, the subgraph H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize Hamiltonian Cycle and hence is NP-complete. In fact, the Connected f-Factor problem remains NP-complete even when f(v) is at least nϵ for each vertex v and ϵ c, the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c ≤ 1. We also show that when c > 1, the problem is NP-intermediate. © Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider.

关键词： Computational complexity

Computing Hive Plots: A Combinatorial Framework

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Nöllenburg, Martin Wallinger, Markus Algorithms and Complexity Group TU Wien Austria

Hive plots are a graph visualization style placing vertices on a set of radial axes emanating from a common center and drawing edges as smooth curves connecting their respective endpoints. In previous work on hive plots, assignment to an axis and vertex positions on each axis were determined based on selected vertex attributes and the order of axes was prespecified. Here, we present a new framework focusing on combinatorial aspects of these drawings to extend the original hive plot idea and optimize visual properties such as the total edge length and the number of edge crossings in the resulting hive plots. Our framework comprises three steps: (1) partition the vertices into multiple groups, each corresponding to an axis of the hive plot;(2) optimize the cyclic axis order to bring more strongly connected groups near each other;(3) optimize the vertex ordering on each axis to minimize edge crossings. Each of the three steps is related to a well-studied, but NP-complete computational problem. We combine and adapt suitable algorithmic approaches, implement them as an instantiation of our framework and show in a case study how it can be applied in a practical setting. Furthermore, we conduct computational experiments to gain further insights regarding algorithmic choices of the framework. The code of the implementation and a prototype web application can be found on OSF1 © 2023, CC BY.

关键词： Optimization

A Time Leap Challenge for SAT-Solving 26th

学校读者我要写书评

暂无评论

A Time Leap Challenge for SAT-Solving

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

作者： Fichte, Johannes K. Hecher, Markus Szeider, Stefan School of Engineering Sciences TU Dresden Dresden Germany Database and Artificial Intelligence Group TU Wien Vienna Austria Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

We compare the impact of hardware advancement and algorithm advancement for SAT-solving over the last two decades. In particular, we compare 20-year-old SAT-solvers on new computer hardware with modern SAT-solvers on 20-year-old hardware. Our findings show that the progress on the algorithmic side has at least as much impact as the progress on the hardware side. © 2020, Springer Nature Switzerland AG.

关键词： Computer hardware

Parameterized complexity of Efficient Sortation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ganian, Robert Hoang, Hung P. Wietheger, Simon TU Vienna Algorithms and Complexity Group Austria

A crucial challenge arising in the design of large-scale logistical networks is to optimize parcel sortation for routing. We study this problem under the recent graph-theoretic formalization of Van Dyk, Klause, Koenemann and Megow (IPCO 2024). The problem asks-given an input digraph D (the fulfillment network) together with a set of commodities represented as source-sink tuples-for a minimum-outdegree subgraph H of the transitive closure of D that contains a source-sink route for each of the commodities. Given the underlying motivation, we study two variants of the problem which differ in whether the routes for the commodities are assumed to be given, or can be chosen arbitrarily. We perform a thorough parameterized analysis of the complexity of both problems. Our results concentrate on three fundamental parameterizations of the problem: 1. When attempting to parameterize by the target outdegree of H, we show that the problems are paraNP-hard even in highly restricted cases;2. When parameterizing by the number of commodities, we utilize Ramsey-type arguments and color-coding techniques to obtain parameterized algorithms for both problems;3. When parameterizing by the structure of D, we establish fixed-parameter tractability for both problems w.r.t. treewidth, maximum degree and the maximum routing length. We combine this with lower bounds which show that omitting any of the three parameters results in paraNPhardness. © 2024, CC BY.

关键词： Parameterization

Crossing Minimization in Time Interval Storylines

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Dobler, Alexander Nöllenburg, Martin Stojanovic, Daniel Villedieu, Anaïs Wulms, Jules Algorithms and Complexity Group TU Wien Austria

Storyline visualizations are a popular way of visualizing characters and their interactions over time: Characters are drawn as x-monotone curves and interactions are visualized through close proximity of the corresponding character curves in a vertical strip. Existing methods to generate storylines assume a total ordering of the interactions, although real-world data often do not contain such a total order. Instead, multiple interactions are often grouped into coarser time intervals such as years. We exploit this grouping property by introducing a new model called storylines with time intervals and present two methods to minimize the number of crossings and horizontal space usage. We then evaluate these algorithms on a small benchmark set to show their effectiveness. © 2023, CC BY.

关键词：

Breaking Symmetries with RootClique and LexTopSort 26th

学校读者我要写书评

暂无评论

Breaking Symmetries with RootClique and LexTopSort

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

ISBN: (纸本)9783030584740

Bounded fractional hypertree width is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Fichte et al. (CP 2018) presented a robust and scalable method for finding optimal fractional hypertree decompositions, based on an encoding to SAT Modulo Theory (SMT). In this paper, we provide an in-depth study of two powerful symmetry breaking predicates that allow us to further speed up the SMT-based decomposition: RootClique fixes the root of the decomposition tree;LexTopSort fixes the elimination ordering with respect to an underlying DAG. We perform an extensive empirical evaluation of both symmetry-breaking predicates with respect to the primal graph (which is known in advance) and the induced graph (which is generated during the search). © 2020, Springer Nature Switzerland AG.

关键词： Constraint satisfaction problems

MySemCloud: Semantic-aware Word Cloud Editing

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Huber, Michael Nöllenburg, Martin Villedieu, Anaïs The Algorithms and Complexity Group at TU Wien Austria

Word clouds are a popular text visualization technique that summarize an input text by displaying its most important words in a compact image. The traditional layout methods do not take proximity effects between words into account;this has been improved in semantic word clouds, where relative word placement is controlled by edges in a word similarity graph. We introduce MySemCloud, a new human-in-the-loop tool to visualize and edit semantic word clouds. MySemCloud lets users perform computer-assisted local moves of words, which improve or at least retain the semantic quality. To achieve this, we construct a word similarity graph on which a system of forces is applied to generate a compact initial layout with good semantic quality. The force system also allows us to maintain these attributes after each user interaction, as well as preserve the user’s mental map. The tool provides algorithmic support for the editing operations to help the user enhance the semantic quality of the visualization, while adjusting it to their personal preference. We show that MySemCloud provides high user satisfaction as well as permits users to create layouts of higher quality than state-of-the-art semantic word cloud generation tools. © 2023, CC BY.

关键词： Visualization

A Note on the complexity of One-Sided Crossing Minimization of Trees

学校读者我要写书评

暂无评论

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

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