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

Planarizing Graphs and their Drawings by Vertex Splitting

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Nöllenburg, Martin Sorge, Manuel Terziadis, Soeren Villedieu, Anaïs Wu, Hsiang-Yun Wulms, Jules Algorithms and Complexity Group Tu Wien Vienna Austria Research Unit of Computer Graphics Tu Wien Vienna Austria St. Pölten University of Applied Sciences Austria

The splitting number of a graph G = (V, E) is the minimum number of vertex splits required to turn G into a planar graph, where a vertex split removes a vertex v ∈ V, introduces two new vertices v1, v2, and distributes the edges formerly incident to v among v1, v2. The splitting number problem is known to be NP-complete for abstract graphs and we provide a non-uniform fixed-parameter tractable (FPT) algorithm for this problem. We then shift focus to the splitting number of a given topological graph drawing in R2, where the new vertices resulting from vertex splits must be re-embedded into the existing drawing of the remaining graph. We show NP-completeness of this embedded splitting number problem, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition. © 2022, CC BY.

关键词： Drawing (graphics)

Fully Dynamic Maximum Independent Sets of Disks in Polylogarithmic Update Time 40

学校读者我要写书评

暂无评论

Fully Dynamic Maximum Independent Sets of Disks in Polylogar...

40th International Symposium on Computational Geometry, SoCG 2024

作者： Bhore, Sujoy Nöllenburg, Martin Tóth, Csaba D. Wulms, Jules Department of Computer Science and Engineering Indian Institute of Technology Bombay Mumbai India Institute of Logic and Computation Algorithms and Complexity Group TU Wien Austria Department of Mathematics California State University Northridge Los AngelesCA United States Department of Computer Science Tufts University MedfordMA United States Department of Mathematics and Computer Science TU Eindhoven Netherlands

ISBN: (纸本)9783959773164

A fundamental question is whether one can maintain a maximum independent set (MIS) in polylogarithmic update time for a dynamic collection of geometric objects in Euclidean space. For a set of intervals, it is known that no dynamic algorithm can maintain an exact MIS in sublinear update time. Therefore, the typical objective is to explore the trade-off between update time and solution size. Substantial efforts have been made in recent years to understand this question for various families of geometric objects, such as intervals, hypercubes, hyperrectangles, and fat objects. We present the first fully dynamic approximation algorithm for disks of arbitrary radii in the plane that maintains a constant-factor approximate MIS in polylogarithmic expected amortized update time. Moreover, for a fully dynamic set of n unit disks in the plane, we show that a 12-approximate MIS can be maintained with worst-case update time O(log n), and optimal output-sensitive reporting. This result generalizes to fat objects of comparable sizes in any fixed dimension d, where the approximation ratio depends on the dimension and the fatness parameter. Further, we note that, even for a dynamic set of disks of unit radius in the plane, it is impossible to maintain O(1 + Ε)-approximate MIS in truly sublinear update time, under standard complexity assumptions. Our results build on two recent technical tools: (i) The MIX algorithm by Cardinal et al. (ESA 2021) that can smoothly transition from one independent set to another;hence it suffices to maintain a family of independent sets where the largest one is an O(1)-approximate MIS. (ii) A dynamic nearest/farthest neighbor data structure for disks by Kaplan et al. (DCG 2020) and Liu (SICOMP 2022), which generalizes the dynamic convex hull data structure by Chan (JACM 2010), and quickly yields a "replacement" disk (if any) when a disk in one of our independent sets is deleted. © Sujoy Bhore, Martin Nöllenburg, Csaba D. Tóth, and Jules Wulms.

关键词： Data structures

Extending Nearly Complete 1-Planar Drawings in Polynomial Time

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Klute, Fabian Nöllenburg, Martin Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Vienna Austria Deptartment of Information and Computing Sciences Utrecht University Netherlands

The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph G, a connected subgraph H of G and a drawing H of H, the extension problem asks whether H can be extended into a drawing of G while maintaining some desired property of the drawing (e.g., planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when H can be obtained from G by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision *** Codes 68R10 Copyright © 2020, The Authors. All rights reserved.

关键词： Graph theory

On the upward book thickness problem: Combinatorial and complexity results

学校读者我要写书评

暂无评论

arXiv 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 Italy Algorithms and Complexity Group TU Wien Vienna Austria

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, CC BY.

关键词： Graphic methods

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

On finding highly connected spanning subgraphs

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Basavaraju, Manu Misra, Pranabendu Ramanujan, M.S. Saurabh, Saket Department of Computer Science and Engineering NITK Surathkal India Institute of Mathematical Sciences HBNI India Algorithms and Complexity Group TU Wien Vienna Austria Department of Informatics University of Bergen Norway

In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruv for every pair of vertices u, v ∈ V (G). The objective is to construct a subgraph H of minimum weight which contains ruv edge-disjoint (or node-disjoint) u-v paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. An important restriction of this problem is the case when the connectivity demands are equal for every pair of vertices in the graph. In this paper, we consider the the edge-connectivity version of this problem which is called the λ-Edge Connected Subgraph (λ-ECS) problem. In this problem, we are given a λ-edge connected (di)graph G with a non-negative weight function w on the edges and an integet k, and the objective is to find a minimum weight spanning subgraph H that is also λ-edge connected, and has at upto k fewer edges than G. In other words, we are asked to compute a maximum weight subset of edges, of cardinality upto k, which may be safely deleted from G. Motivated by this question, we investigate the connectivity properties of λ-edge connected (di)graphs and obtain algorithmically significant structural results. One of our central structural results can be roughly stated as follows. In polynomial time, one can either find a set of k edges which can be deleted from the given (di)graph without violating the connectivity constraints, or correctly conclude that the (di)graph contains only O(λk3) 'interesting' edges. We demonstrate the importance of our structural results by presenting an algorithm running in time 2O(k log k)|V (G)|O(1) for λ-ECS, thus proving its fixed-parameter tractability. We follow up on this result and obtain the first polynomial compression for λ-ECS on unweighted graphs. As a consequence, we also obtain the first fixed parameter tractable algorithm, and a polynomial kernel for a parameterized version of the classic Mininum Equi

关键词： Graph theory

The Parameterized complexity of Coordinated Motion Planning

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad 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

In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target—prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n2 − 1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish—as a simpler case—the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids. © 2023, CC BY.

关键词： Robots

Finding large matchings in 1-planar graphs of minimum degree 3

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Biedl, Therese Klute, Fabian David R. Cheriton School of Computer Science University of Waterloo WaterlooONN2L 1A2 Canada Algorithms and Complexity Group TU Wien Austria

A matching is a set of edges without common endpoint. It was recently shown that every 1-planar graph (i.e., a graph that can be drawn in the plane with at most one crossing per edge) that has minimum degree 3 has a matching of size at least n+12/7 , and this is tight for some graphs. The proof did not come with an algorithm to find the matching more efficiently than a general-purpose maximum-matching algorithm. In this paper, we give such an algorithm. More generally, we show that any matching that has no augmenting paths of length 9 or less has size at least n+12/7 in a 1-planar graph with minimum degree 3. Copyright © 2020, The Authors. All rights reserved.

关键词： Machine learning

The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k ≥ 5

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Heimann, Sophia Hoang, Hung P. Hougardy, Stefan Research Institute for Discrete Mathematics University of Bonn Germany Algorithms and Complexity Group Faculty of Informatics TU Wien Austria Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics University of Bonn Germany

The k-Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most k edges in the tour with the same number of edges to obtain a better tour. Krentel (FOCS 1989) showed that the Traveling Salesman Problem with the k-Opt neighborhood is complete for the class PLS (polynomial time local search) and that the k-Opt algorithm can have exponential running time for any pivot rule. However, his proof requires k 1000 and has a substantial gap. We show the two properties above for a much smaller value of k, addressing an open question by Monien, Dumrauf, and Tscheuschner (ICALP 2010). In particular, we prove the PLS-completeness for k ≥ 17 and the exponential running time for k ≥ *** Codes 68W25, 68W40, 68Q25, 90C27 © 2024, CC BY-NC-ND.

关键词： Traveling salesman problem