5 results
Now showing1 - 5 of 5
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Compact cactus representations of all non-trivial min-cuts(2021-11-15); ; Recently, Kawarabayashi and Thorup presented the first deterministic edge-connectivity recognition algorithm in near-linear time. A crucial step in their algorithm uses the existence of vertex subsets of a simple graph G on n vertices whose contractions leave a multigraph with Õ(n∕δ) vertices and Õ(n) edges that preserves all non-trivial min-cuts of G, where δ is the minimum degree of G and Õ hides logarithmic factors. We present a simple argument that improves this contraction-based sparsifier by eliminating the poly-logarithmic factors, that is, we show a contraction-based sparsification that leaves O(n∕δ) vertices and O(n) edges, preserves all non-trivial min-cuts and can be computed in near-linear time Õ(m), where m is the number of edges of G. We also obtain that every simple graph has O((n∕δ)2) non-trivial min-cuts. Our approach allows to represent all non-trivial min-cuts of a graph by a cactus representation, whose cactus graph has O(n∕δ) vertices. Moreover, this cactus representation can be derived directly from the standard cactus representation of all min-cuts in linear time. We apply this compact structure to show that all min-cuts can be explicitly listed in Õ(m)+O(n2∕δ) time for every simple graph, which improves the previous best time bound O(nm) given by Gusfield and Naor.Publicationtype: Journal Article79 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Cycle spectra of contraction-critically 4-connected planar graphsMotivated by the long-standing and wide open pancyclicity conjectures of Bondy and Malkevitch, we study the cycle spectra of contraction-critically 4-connected planar graphs. We show that every contraction-critically 4-connected planar graph on n vertices contains a cycle of length k for every k∈⌊n2⌋-⌈n108⌉,⋯,⌊n2⌋+⌊n36⌋∪23n,⋯,n.Publicationtype: Journal Article142 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Shortness coefficient of cyclically 4-edge-connected cubic graphs(2020-02-07); ; ; Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most76 77. Recently, this was improved to (Formula Presented) and the question was raised whether this can be strengthened to 42, a natural bound inferred from one of the Faulkner-Younger graphs. We prove that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 37 38 and that we also get the same value for cyclically 4-edge-connected cubic graphs of genus g for any prescribed genus g ≥ 0. We also show that45 46 is an upper bound for the shortness coefficient of cyclically 4-edge-connected cubic graphs of genus g with face lengths bounded above by some constant larger than 22 for any prescribed g ≥ 0.Publicationtype: Journal ArticleScopus© Citations 1 154 115 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A cut tree representation for pendant pairs(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2018-12); Two vertices v and w of a graph G are called a pendant pair if the maximal number of edge-disjoint paths in G between them is precisely mind(v), d(w), where d denotes the degree function. The importance of pendant pairs stems from the fact that they are the key ingredient in one of the simplest and most widely used algorithms for the minimum cut problem today. Mader showed 1974 that every simple graph with minimum degree δ contains Ω(δ2) pendant pairs; this is the best bound known so far. We improve this result by showing that every simple graph G with minimum degree δ ≥ 5 or with edge-connectivity λ ≥ 4 or with vertex-connectivity κ ≥ 3 contains in fact Ω(δ|V |) pendant pairs. We prove that this bound is tight from several perspectives, and that Ω(δ|V |) pendant pairs can be computed efficiently, namely in linear time when a Gomory-Hu tree is given. Our method utilizes a new cut tree representation of graphs.Publicationtype: Conference Paper70 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Longest cycles in cyclically 4-edge-connected cubic planar graphs(Centre for Discrete Mathematics and Computing, Univ. of Queensland, 2018); Grünbaum and Malkevitch proved in 1976 that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 76/77. We prove that it is at most 359/366 (< 52/53).Publicationtype: Journal Article55