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

Unit disk representations of embedded trees, outerplanar and multi-legged graphs

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Löffler, Maarten Nickel, Soeren Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Department of Computing and Information Sciences Utrecht University Algorithms and Complexity Group TU Wien Vienna Austria

A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP-hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that it can be decided in linear time if a lobster graph admits a weak UDC, which permits intersections between disks of non-adjacent vertices. © 2021, CC BY.

关键词： Trees (mathematics)

Parameterized algorithms for Generalizations of Directed Feedback Vertex Set∗

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Göke, Alexander Marx, Dániel Mnich, Matthias TU Hamburg Institute for Algorithms and Complexity Hamburg Germany Max-Planck-Institut für Informatik Saarbrücken Germany TU Hamburg Institute for Algorithms and Complexity Hamburg Germany

The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp’s 21 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. [STOC 2008, J. ACM 2008] showed its fixed-parameter tractability via a 4kk!nO(1)-time algorithm, where k = |S|. Here we show fixed-parameter tractability of two generalizations of DFVS: • Find a smallest vertex set S such that every strong component of G − S has size at most s: we give an algorithm solving this problem in time 4k(ks + k + s)! · nO(1). This generalizes an algorithm by Xiao [JCSS 2017] for the undirected version of the problem. • Find a smallest vertex set S such that every non-trivial strong component of G − S is 1-out-regular: we give an algorithm solving this problem in time 2O(k3) · nO(1). We also solve the corresponding arc versions of these problems by fixed-parameter algorithms. Copyright © 2020, The Authors. All rights reserved.

关键词： Directed graphs

Teleportation of quantum coherence

学校读者我要写书评

暂无评论

Physical Review A 2023年第4期108卷 042620-042620页

作者： Sohail Arun K. Pati Vijeth Aradhya Indranil Chakrabarty Subhasree Patro Quantum Information and Computation Group Harish-Chandra Research Institute A CI of Homi Bhabha National Institute Chhatnag Road Jhunsi Prayagraj 211019 India Centre for Quantum Science and Technology International Institute of Information Technology Hyderabad Gachibowli Hyderabad-500032 Telangana India Center for Security Theory and Algorithmic Research International Institute of Information Technology Hyderabad Gachibowli Hyderabad-500032 Telangana India Department of Computer Science National University of Singapore 117417 Singapore Computer science and physics department Utrecht University 3584 CS Utrecht The Netherlands Algorithms and complexity group QuSoft Centrum Wiskunde and Informatica 1098XG Amsterdam The Netherlands

We investigate whether it is possible to teleport the coherence of an unknown quantum state from Alice to Bob by communicating a smaller number of classical bits in comparison to what is required for teleporting an unknown quantum state. We find that we cannot achieve perfect teleportation of coherence with one bit of classical communication for an arbitrary qubit. However, we find that if the qubit is partially known, i.e., chosen from the equatorial and polar circles of the Bloch sphere, then teleportation of coherence is possible with the transfer of one cbit of information when we have maximally entangled states as a shared resource. In the case of the resource being a nonmaximally entangled state, we can teleport the coherence with a certain probability of success. In a general teleportation protocol for coherence, we derive a compact formula for the final state at Bob's laboratory in terms of the composition of the completely positive maps corresponding to the shared resource state and a joint positive operator-valued measure (POVM) performed by Alice on her qubit and the unknown state. Using this formula, we show that teleportation of the coherence of a partially known state with real matrix elements is perfectly possible with the help of a maximally entangled state as a resource. Furthermore, we explore the teleportation of coherence with Werner states and show that even when Werner states become separable, the amount of teleported coherence is nonzero, implying the possibility of teleportation of coherence without entanglement.

关键词： Quantum coherence & coherence measures Quantum communication Quantum correlations in quantum information Quantum information theory Quantum protocols

Gerrymandering on graphs: Computational complexity and parameterized algorithms

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Gupta, Sushmita Jain, Pallavi Panolan, Fahad Roy, Sanjukta Saurabh, Saket Institute of Mathematical Science HBNI India Indian Institute of Technology Jodhpur India Indian Institute of Technology Hyderabad India Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Science HBNI India University of Bergen Norway

The practice of partitioning a region into areas to favor a particular candidate or a party in an election has been known to exist for the last two centuries. This practice is commonly known as gerrymandering. Recently, the problem has also attracted a lot of attention from complexity theory perspective. In particular, Cohen-Zemach et al. [AAMAS 2018] proposed a graph theoretic version of gerrymandering problem and initiated an algorithmic study around this, which was continued by Ito et al. [AAMAS 2019]. In this paper we continue this line of investigation and resolve an open problem in the literature, as well as move the algorithmic frontier forward by studying this problem in the realm of parameterized complexity. Our contributions in this article are two-fold, conceptual and computational. We first resolve the open question posed by Ito et al. [AAMAS 2019] about the computational complexity of gerrymandering when the input graph is a path. Next, we propose a generalization of the model studied in [AAMAS 2019], where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function wv : C → Z+ for each voter v ∈ V (G) representing the preference of the voter over the candidates, a distinguished candidate p ∈ C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pairwise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts the vertex set needs to be partitioned (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k = 2, m = 2, and G is either a complete bipartite graph (in fact K2,n, a complete bipartite graphs with one side of size 2 and the other of size n) or a complete graph. This hardness result implies that we cannot hope to have an algorithm wit

关键词： Graph theory

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

学校读者我要写书评

暂无评论

Discrete Mathematics and Theoretical Computer Science 2025年 272卷

作者： Dumas, Maël Perez, Anthony Rocton, Mathis Todinca, Ioan Institute of Informatics University of Warsaw Warsaw Poland Université d’Orléans INSA CVL LIFO UR 4022 Orléans 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: © 2025 by the author(s)

关键词： Graphic methods

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

The most general structure of graphs with hamiltonian or hamiltonian connected square

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Ekstein, Jan Fleischner, Herbert Department of Mathematics European Centre of Excellence Ntis - New Technologies for the Information Society Faculty of Applied Sciences University of West Bohemia Pilsen Technická 8 Plzeň306 14 Czech Republic Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Favoritenstrasse 9 - 11 Wien1040 Austria

On the basis of recent results on hamiltonicity, [4], and hamiltonian connectedness, [8], in the square of a 2-block, we determine the most general block-cutvertex structure a graph G may have in order to guarantee that G2 is hamiltonian, hamiltonian connected, respectively. Such an approach was already developed in [9] for hamiltonian total *** Codes 05C38, 05C45 © 2022, CC BY.

关键词： Hamiltonians

Parameterized study of STEINER TREE on unit disk graphs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Carmi, Paz Kolay, Sudeshna Kolay, Sudeshna Algorithms and Complexity Group Tu Wien Vienna Austria Ben-Gurion University of the Negev Beersheba Israel Indian Institute of Technology Kharagpur

We study the STEINER TREE problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V (G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \ R. The vertices of R are referred to as terminals and the vertices of V (G) \ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the STEINER TREE problem on unit disk graphs can be solved in nO(√t+k)time. We also show that the STEINER TREE problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2O(k)nO(1). In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [16]. We mention that the algorithmic results can be made to work for STEINER TREE on disk graphs with bounded aspect ratio. Finally, we prove that STEINER TREE on disk graphs parameterized by k is W[1]-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： Hardness

Solving the Steiner Tree Problem with few Terminals

学校读者我要写书评

暂无评论

Solving the Steiner Tree Problem with few Terminals

International Conference on Tools for Artificial Intelligence (ICTAI)

作者： Johannes K. Fichte Markus Hecher André Schidler Institute of Artificial Intelligence TU Dresden Dresden Germany University of Potsdam Germany Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (数字)9781728192284

ISBN: (纸本)9781728185361

The Steiner tree problem is a well-known problem in network design, routing, and VLSI design. Given a graph, edge costs, and a set of dedicated vertices (terminals), the Steiner tree problem asks to output a sub-graph that connects all terminals at minimum cost. A state-of-the-art algorithm to solve the Steiner tree problem by means of dynamic programming is the Dijkstra-Steiner algorithm. The algorithm builds a Steiner tree of the entire instance by systematically searching for smaller instances, based on subsets of the terminals, and combining Steiner trees for these smaller instances. The search heavily relies on a guiding heuristic function in order to prune the search space. However, to ensure correctness, this algorithm allows only for limited heuristic functions, namely, those that satisfy a so-called consistency condition. In this paper, we enhance the Dijkstra-Steiner algorithm and establish a revisited algorithm, called DS*. The DS* algorithm allows for arbitrary lower bounds as heuristics relaxing the previous condition on the heuristic function. Notably, we can now use linear programming based lower bounds. Further, we capture new requirements for a heuristic function in a condition, which we call admissibility. We show that admissibility is indeed weaker than consistency and establish correctness of the DS* algorithm when using an admissible heuristic function. We implement DS* and combine it with modern preprocessing, resulting in an open-source solver (DS*Solve). Finally, we compare its performance on standard benchmarks and observe a competitive behavior.

关键词： Steiner trees Heuristic algorithms Very large scale integration Tools Routing Standards Open source software