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

Counting linear extensions: Parameterizations by treewidth 24

学校读者我要写书评

暂无评论

Counting linear extensions: Parameterizations by treewidth

24th Annual European Symposium on algorithms, ESA 2016

作者： Eiben, Eduard Ganian, Robert Kangas, Kustaa Ordyniak, Sebastian Algorithms and Complexity Group TU Wien Vienna Austria Helsinki Institute for Information Technology Department of Computer Science University of Helsinki Finland

ISBN: (纸本)9783959770156

We consider the #P-complete problem of counting the number of linear extensions of a poset (#LE);a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of #LE parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e., the cover and the incomparability graph. Our main result shows that #LE is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact algorithms. On the positive side we show that #LE becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph. © Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak.

关键词： Parameterization

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

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

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

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

Drawing Shortest Paths in Geodetic Graphs

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2022年第3期26卷 353-361页

作者： Cornelsen, Sabine Pfister, Maximilian Förster, Henry Gronemann, Martin Hoffmann, Michael Kobourov, Stephen Schneck, Thomas University of Konstanz Germany University of Tübingen Germany Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science ETH Zürich Switzerland Department of Computer Science University of Arizona United States

Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph G, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of G, i.e., a drawing of G in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing. On the positive side we show that geodetic graphs admit a philogeodetic drawing if both the diameter and the density are very low. © 2022, Brown University. All rights reserved.

关键词： Graphic methods