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

On structural parameterizations of the edge disjoint paths problem 28

学校读者我要写书评

暂无评论

On structural parameterizations of the edge disjoint paths p...

28th International Symposium on algorithms and Computation, ISAAC 2017

作者： Ganian, Robert Ordyniak, Sebastian Sridharan, Ramanujan Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959770545

In this paper we revisit the classical Edge Disjoint Paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P. Our focus lies on structural parameterizations for the problem that allow for efficient (polynomial-Time or fpt) algorithms. As our first result, we answer an open question stated in Fleszar, Mnich, and Spoerhase (2016), by showing that the problem can be solved in polynomial time if the input graph has a feedback vertex set of size one. We also show that EDP parameterized by the treewidth and the maximum degree of the input graph is fixed-parameter tractable. Having developed two novel algorithms for EDP using structural restrictions on the input graph, we then turn our attention towards the augmented graph, i.e., the graph obtained from the input graph after adding one edge between every terminal pair. In constrast to the input graph, where EDP is known to remain NP-hard even for treewidth two, a result by Zhou et al. (2000) shows that EDP can be solved in non-uniform polynomial time if the augmented graph has constant treewidth;we note that the possible improvement of this result to an fpt-Algorithm has remained open since then. We show that this is highly unlikely by establishing the W[1]-hardness of the problem parameterized by the treewidth (and even feedback vertex set) of the augmented graph. Finally, we develop an fpt-Algorithm for EDP by exploiting a novel structural parameter of the augmented graph.

关键词： Parameterization

The parameterized complexity of clustering incomplete data

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan 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 University of Leeds School of Computing Leeds United Kingdom

We study fundamental clustering problems for incomplete data. Specifically, given a set of incomplete d-dimensional vectors (representing rows of a matrix), the goal is to complete the missing vector entries in a way that admits a partitioning of the vectors into at most k clusters with radius or diameter at most r. We give tight characterizations of the parameterized complexity of these problems with respect to the parameters k, r, and the minimum number of rows and columns needed to cover all the missing entries. We show that the considered problems are fixed-parameter tractable when parameterized by the three parameters combined, and that dropping any of the three parameters results in parameterized intractability. A byproduct of our results is that, for the complete data setting, all problems under consideration are fixed-parameter tractable parameterized by k + r. Copyright © 2019, The Authors. All rights reserved.

关键词： Parameterization

Parameterized algorithms for the matrix completion problem

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University Chicago United States

We consider two matrix completion problems, in which we are given a matrix with missing entries and the task is to complete the matrix in a way that (1) minimizes the rank, or (2) minimizes the number of distinct rows. We study the parameterized complexity of the two aforementioned problems with respect to several parameters of interest, including the minimum number of matrix rows, columns, and rows plus columns needed to cover all missing entries. We obtain new algorithmic results showing that, for the bounded domain case, both problems are fixed-parameter tractable with respect to all aforementioned parameters. We complement these results with a lower-bound result for the unbounded domain case that rules out fixed-parameter tractability w.r.t. some of the parameters under consideration. Copyright © 2018, The Authors. All rights reserved.

关键词： Matrix algebra

A best possible result for the square of a 2-block to be hamiltonian

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Ekstein, Jan Fleischner, Herbert Department of Mathematics and 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 Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Favoritenstrasse 9-11 Wien1040 Austria

It is shown that for any choice of four different vertices x1,...,x4 in a 2-block G of order p > 3, there is a hamiltonian cycle in G2 containing four different edges xiyi of E(G) for certain vertices yi, i = 1,2,3... 详细信息

关键词： Hamiltonians

Hamiltonian cycles in planar cubic graphs with facial 2−factors, and a new partial solution of Barnette's Conjecture

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Gh, Behrooz Bagheri Feder, Tomas Fleischner, Herbert Subi, Carlos Algorithms and Complexity Group Vienna University of Technology 268 Waverley St. Palo AltoCA94301 United States

We study the existence of hamiltonian cycles in plane cubic graphs G having a facial 2−factor Q. Thus hamiltonicity in G is transformed into the existence of a (quasi) spanning tree of faces in the contraction G/Q. In particular, we study the case where G is the leapfrog extension (called vertex envelope in (Discrete Math., 309(14):4793-4809, 2009)) of a plane cubic graph G0. As a consequence we prove hamiltonicity in the leapfrog extension of planar cubic cyclically 4−edge-connected bipartite graphs. This and other results of this paper establish partial solutions of Barnette's Conjecture according to which every 3−connected cubic planar bipartite graph is hamiltonian. These results go considerably beyond Goodey's result on this topic (Israel J. Math., 22:52-56, 1975). Copyright © 2018, The Authors. All rights reserved.

关键词： Hamiltonians

Path-contractions, edge deletions and connectivity preservation 25

学校读者我要写书评

暂无评论

Path-contractions, edge deletions and connectivity preservat...

25th European Symposium on algorithms, ESA 2017

作者： Gutin, Gregory Ramanujan, M.S. Reidl, Felix Wahlström, Magnus Algorithms and Complexity Group TU Wien Vienna Austria Royal Holloway University Egham United Kingdom

ISBN: (纸本)9783959770491

We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, Vertexdeletion Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while deleting exactly k vertices, and Path-contraction Preserving Strong Connectivity, in which the operation of path contraction on arcs is used instead. The parameterized tractability of this last problem was posed in [Bang-Jensen and Yeo, Discrete Applied Math 2008] as an open question and we answer it here in the negative: both variants of preserving strong connectivity are W[1]-hard. Preserving biconnectivity, on the other hand, turns out to be fixed parameter tractable (FPT) and we provide an FPT algorithm that solves Weighted Biconnectivity Deletion. Further, we show that the unweighted case even admits a randomized polynomial kernel. All our results provide further interesting data points for the systematic study of connectivitypreservation constraints in the parameterized setting.

关键词： Undirected graphs

Partitioning graph drawings and triangulated simple polygons into greedily routable regions

学校读者我要写书评

暂无评论

International Journal of Computational Geometry and Applications 2017年第1-2期27卷 121-158页

作者： Nöllenburg, Martin Prutkin, Roman Rutter, Ignaz Algorithms and Complexity Group TU Wien Vienna Austria Institute of Theoretical Informatics Karlsruhe Institute of Technology Karlsruhe Germany Algorithms and Visualization WandI Technische Universiteit Eindhoven Eindhoven Netherlands

A greedily routable region (GRR) is a closed subset of ℝ2, in which any destination point can be reached from any starting point by always moving in the direction with maximum reduction of the distance to the destination in each point of the path. Recently, Tan and Kermarrec proposed a geographic routing protocol for dense wireless sensor networks based on decomposing the network area into a small number of interior-disjoint GRRs. They showed that minimum decomposition is NP-hard for polygonal regions with holes. We consider minimum GRR decomposition for plane straight-line drawings of graphs. Here, GRRs coincide with self-approaching drawings of trees, a drawing style which has become a popular research topic in graph drawing. We show that minimum decomposition is still NP-hard for graphs with cycles and even for trees, but can be solved optimally for trees in polynomial time, if we allow only certain types of GRR contacts. Additionally, we give a 2-approximation for simple polygons, if a given triangulation has to be respected. © 2017 World Scientific Publishing Company.

关键词： Decomposing graph drawings Greedy region decomposition Greedy routing in wireless sensor networks Increasing-chord drawings

Hybrid 2D/3D photonic integration for non-planar circuit topologies

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Nesic, Aleksandar Blaicher, Matthias Hoose, Tobias Hofmann, Andreas Lauermann, Matthias Kutuvantavida, Yasar Nöllenburg, Martin Randel, Sebastian Freude, Wolfgang Koos, Christian Engesserstrasse 5 Karlsruhe76131 Germany Hermann-vonHelmholtz-Platz 1 Eggenstein-Leopoldshafen76344 Germany Hermann-von-Helmholtz-Platz 1 Eggenstein-Leopoldshafen76344 Germany Vanguard Photonics GmbH Gablonzer Strasse 10 Karlsruhe76185 Germany TU Wien Institute of Logic and Computation Algorithms and Complexity Group Favoritenstrasse 9-11 Vienna1040 Austria

Complex photonic integrated circuits (PIC) may have strongly non-planar topologies that require waveguide crossings (WGX) when realized in single-layer integration platforms. The number of WGX increases rapidly with the complexity of the circuit, in particular when it comes to highly interconnected optical switch topologies. Here, we present a concept for WGX-free PIC that rely on 3D-printed freeform waveguide overpasses (WOP). We experimentally demonstrate the viability of our approach using the example of a 4 × 4 switch-and-select (SAS) circuit realized on the silicon photonic platform. We further present a comprehensive graph-theoretical analysis of different n × n SAS circuit topologies. We find that for increasing port counts n of the SAS circuit, the number of WGX increases with n4, whereas the number of WOP increases only in proportion to n2. Copyright © 2019, The Authors. All rights reserved.

关键词： Timing circuits

Towards a polynomial kernel for directed feedback vertex set 42

学校读者我要写书评

暂无评论

Towards a polynomial kernel for directed feedback vertex set

42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017

作者： Bergougnoux, Benjamin Eiben, Eduard Ganian, Robert Ordyniak, Sebastian Ramanujan, M.S. Université Clermont Auvergne LIMOS CNRS Aubière France Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959770460

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008];since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus. © Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan;licensed under Creative Commons License CC-BY.

关键词： Directed graphs