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

Untangling Circular Drawings: algorithms and complexity 32

学校读者我要写书评

暂无评论

Untangling Circular Drawings: Algorithms and Complexity

32nd International Symposium on algorithms and Computation, ISAAC 2021

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Austria Universität Passau Germany Research Unit of Computer Graphics TU Wien Austria

ISBN: (纸本)9783959772143

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that need to be shifted to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift◦(δG) ≤ ⌊n2 ⌋ - 1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu.

关键词： Computational complexity

Parameterized algorithms for Coordinated Motion Planning: Minimizing Energy

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Deligkas, Argyrios Eiben, Eduard Ganian, Robert Kanj, Iyad Ramanujan, M.S. Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Vienna Austria School of Computing DePaul University Chicago United States Department of Computer Science University of Warwick United Kingdom

We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of k robots to their destinations with the aim of minimizing the total energy (i.e., the total length traveled). We develop novel techniques to push beyond previously-established results that were restricted to solid grids. We design a fixed-parameter additive approximation algorithm for this problem parameterized by k alone. This result, which is of independent interest, allows us to prove the following two results pertaining to well-studied coordinated motion planning problems: (1) A fixed-parameter algorithm, parameterized by k, for routing a single robot to its destination while avoiding the other robots, which is related to the famous Rush-Hour Puzzle;and (2) a fixed-parameter algorithm, parameterized by k plus the treewidth of the input graph, for the standard Coordinated Motion Planning (CMP) problem in which we need to route all the k robots to their destinations. The latter of these results implies, among others, the fixed-parameter tractability of CMP parameterized by k on graphs of bounded outerplanarity, which include bounded-height subgrids. We complement the above results with a lower bound which rules out the fixed-parameter tractability for CMP when parameterized by the total energy. This contrasts the recently-obtained tractability of the problem on solid grids under the same parameterization. As our final result, we strengthen the aforementioned fixed-parameter tractability to hold not only on solid grids but all graphs of bounded local treewidth - a class including, among others, all graphs of bounded genus. Copyright © 2024, The Authors. All rights reserved.

关键词： Parameterization

On the Upward Book Thickness Problem: Combinatorial and complexity Results 29th

学校读者我要写书评

暂无评论

On the Upward Book Thickness Problem: Combinatorial and Com...

29th International Symposium on Graph Drawing and Network Visualization, GD 2021

作者： Bhore, Sujoy Da Lozzo, Giordano Montecchiani, Fabrizio Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Roma Tre University Rome Italy Department of Engineering University of Perugia Perugia Italy Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are st-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP-hard for any fixed k≥ 3. We show that the problem, for any k≥ 5, remains NP-hard for graphs whose domination number is O(k), but it is FPT in the vertex cover number. © 2021, Springer Nature Switzerland AG.

关键词： Graphic methods

Graph drawing applications in combinatorial theory of maturity models

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kajzer, Špela Dobler, Alexander Jerebic, Janja Nöllenburg, Martin Orthaber, Joachim Bokal, Drago Faculty of Natural Sciences and Mathematics University of Maribor Slovenia Institute of Mathematics Physics and Mechanics Ljubljana Slovenia Algorithms and Complexity Group TU Wien Austria Faculty of Organizational Sciences University of Maribor Slovenia Institute of Software Technology Graz University of Technology Austria

In this paper, we introduce tiled graphs as models of learning and maturing processes. We show how tiled graphs can combine graphs of learning spaces or antimatroids (partial hypercubes) and maturity models (total orders) to yield models of learning processes. For the visualization of these processes it is a natural approach to aim for certain optimal drawings. We show for most of the more detailed models that the drawing problems resulting from them are NP-complete. The terse model of a maturing process that ignores the details of learning, however, results in a polynomially solvable graph drawing problem. In addition, this model provides insight into the process by ordering the subjects at each test of their maturity. We investigate extremal and random instances of this problem, and provide exact results and bounds on their optimal crossing number. Graph-theoretic models offer two approaches to the design of optimal maturity models given observed data: (1) minimizing intra-subject inconsistencies, which manifest as regressions of subjects, is modeled as the well-known feedback arc set problem. We study the alternative of (2) finding a maturity model by minimizing the inter-subject inconsistencies, which manifest as crossings in the respective drawing. We show this to be NP-complete. © 2024, CC BY.

关键词： Optimization

Signed Double Roman Domination on Cubic Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Iurlano, Enrico Zec, Tatjana Djukanovic, Marko Raidl, Günther R. Algorithms and Complexity Group TU Wien Favoritenstraße 9/1921 Vienna1040 Austria Faculty of Natural Sciences and Mathematics University of Banja Luka Mladena Stojanovića 2 Banja Luka78000 Bosnia and Herzegovina

The signed double Roman domination problem is a combinatorial optimization problem on a graph asking to assign a label from {±1, 2, 3} to each vertex feasibly, such that the total sum of assigned labels is minimized. Here feasibility is given whenever (i) vertices labeled ±1 have at least one neighbor with label in {2, 3};(ii) each vertex labeled −1 has one 3-labeled neighbor or at least two 2-labeled neighbors;and (iii) the sum of labels over the closed neighborhood of any vertex is positive. The cumulative weight of an optimal labeling is called signed double Roman domination number (SDRDN). In this work, we first consider the problem on general cubic graphs of order n for which we present a sharp n/2 + Θ(1) lower bound for the SDRDN by means of the discharging method. Moreover, we derive a new best upper bound. Observing that we are often able to minimize the SDRDN over the class of cubic graphs of a fixed order, we then study in this context generalized Petersen graphs for independent interest, for which we propose a constraint programming guided proof. We then use these insights to determine the SDRDNs of subcubic 2 × m grid graphs, among other *** Codes 05C78, 05C35, 90C27 © 2023, CC BY.

关键词： Graphic methods

First-order logic in finite domains: Where semantic evaluation competes with SMT solving

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Schreiner, Wolfgang Reichl, Franz-Xaver Johannes Kepler University Linz Austria Algorithms and Complexity Group Tu Wien Austria

In this paper, we compare two alternative mechanisms for deciding the validity of first-order formulas over finite domains supported by the mathematical model checker RISCAL: first, the original approach of "semantic evaluation" (based on an implementation of the denotational semantics of the RISCAL language) and, second, the later approach of SMT solving (based on satisfiability preserving translations of RISCAL formulas to SMT-LIB formulas as inputs for SMT solvers). After a short presentation of the two approaches and a discussion of their fundamental pros and cons, we quantitatively evaluate them, both by a set of artificial benchmarks and by a set of benchmarks taken from real-life applications of RISCAL;for this, we apply the state-of-the-art SMT solvers Boolector, CVC4, Yices, and Z3. Our benchmarks demonstrate that (while SMT solving generally vastly outperforms semantic evaluation), the various SMT solvers exhibit great performance differences. More important, we identify classes of formulas where semantic evaluation is able to compete with (or even outperform) satisfiability solving, outlining some room for improvements in the translation of RISCAL formulas to SMT-LIB formulas as well as in the current SMT technology. © 2021, CC BY.

关键词： Benchmarking

Efficient Approximation of Fractional Hypertree Width

学校读者我要写书评

暂无评论

Efficient Approximation of Fractional Hypertree Width

Annual IEEE Symposium on Foundations of Computer Science

作者： Viktoriia Korchemna Daniel Lokshtanov Saket Saurabh Vaishali Surianarayanan Jie Xue Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science University of California Santa Barbara Santa Barbara USA University of Bergen Bergen Norway Institute of Mathematical Sciences Chennai India New York University Shanghai Shanghai China

ISBN: (数字)9798331516741

ISBN: (纸本)9798331516758

We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input n-vertex m-edge hypergraph $H$ of fractional hypertree width at most $\omega$ , runs in polynomial time and produces a tree decomposition of $H$ of fractional hypertree width $\mathcal{O}(\omega\log n\log\omega)$ , i.e., it is an $\mathcal{O}(\log n\log\omega)$ -approximation algorithm. As an immediate corollary this yields poly-nomial time $\mathcal{O}(\log^algorithmsn\log\omega)$ -approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when $\omega$ is considered a constant. For hypergraphs where every pair of hyperedges have at most $\eta$ vertices in common, the al-gorithm outputs a hypertree decomposition with fractional hypertree width $\mathcal{O}(\eta\omega^algorithms\log\omega)$ and generalized hypertree width $\mathcal{O}(\eta\omega^algorithms\log\omega(\log\eta+\text{log}\omega))$ . This ratio is comparable with the recent algorithm of Lanzinger and Razgon [STACS 2024], which produces a hypertree decomposition with generalized hypertree width ${\mathcal{O}}(\omega^algorithms(\omega+\eta))$ , but uses time (at least) exponential in $\eta$ and $\omega$ . The second algorithm runs in time $n^{\omega}m^{\mathcal{O}(1)}$ and pro-duces a tree decomposition of $H$ of fractional hypertree width $\mathcal{O}(\omega{\mathrm{l}}\text{og}^algorithms\omega)$ . This significantly improves over the $(n+m)^{\mathcal{O}(\omega^algorithms)}$ time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hyper-tree width $\mathcal{O}(\omega^algorithms)$ , both in terms of running time and the approximation ratio. Our main technical contribution, and the k

关键词： Computer science Particle separators Approximation algorithms Polynomials

Polynomial kernels for edge modification problems towards block and strictly chordal graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Dumas, Maël Perez, Anthony Rocton, Mathis Todinca, Ioan LIFO EA 4022 Univ. Orléans INSA Centre Val de Loire France Algorithms and Complexity Group TU Wien Vienna Austria

We consider edge modification problems towards block and strictly chordal graphs, where one is given an undirected graph G = (V, E) and an integer k ∈ N and seeks to edit (add or delete) at most k edges from G to obtain a block graph or a strictly chordal graph. The completion and deletion variants of these problems are defined similarly by only allowing edge additions for the former and only edge deletions for the latter. Block graphs are a well-studied class of graphs and admit several characterizations, e.g. they are diamond-free chordal graphs. Strictly chordal graphs, also referred to as block duplicate graphs, are a natural generalization of block graphs where one can add true twins of cut-vertices. Strictly chordal graphs are exactly dart and gem-free chordal graphs. We prove the NP-completeness for most variants of these problems and provide: • O(k2) vertex-kernels for Block Graph Editing and Block Graph Deletion • O(k3) vertex-kernels for Strictly Chordal Completion and Strictly Chordal Deletion • an O(k4) vertex-kernel for Strictly Chordal Editing © 2022, CC BY.

关键词： Undirected graphs

Tight complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Focke, Jacob Marx, Dániel Inerney, Fionn Mc Neuen, Daniel Sankar, Govind S. Schepper, Philipp Wellnitz, Philip CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria School of Computing Science Simon Fraser University Canada Duke University United States Max Planck Institute for Informatics SIC Germany

For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u) ∩ S| ∈ σ for every u ∈ S, and |N(v) ∩ S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set, Dominating Set, Independent Dominating Set, and many others. In an accompanying paper, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time (cσ,ρ)tw · nO(1) (if a tree decomposition of width tw is given in the input). Here, cσ,ρ is a constant with an intricate dependency on σ and ρ. Despite this intricacy, we show that the algorithms in the accompanying paper are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any Ε > 0, a (cσ,ρ − Ε)tw · nO(1)-algorithm counting the number of (σ, ρ)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well. Copyright © 2023, The Authors. All rights reserved.

关键词： Trees (mathematics)