Compact cactus representations of all non-trivial min-cuts
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Compact cactus representations of all non-trivial min-cuts. / Lo, On Hei S.; Schmidt, Jens M.; Thorup, Mikkel.
I: Discrete Applied Mathematics, Bind 303, 2021, s. 296-304.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Compact cactus representations of all non-trivial min-cuts
AU - Lo, On Hei S.
AU - Schmidt, Jens M.
AU - Thorup, Mikkel
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Cactus representation
KW - Contraction-based sparsification
KW - DAG representation
KW - Min-cuts enumeration
KW - Non-trivial min-cuts
UR - http://www.scopus.com/inward/record.url?scp=85082857967&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2020.03.046
DO - 10.1016/j.dam.2020.03.046
M3 - Journal article
AN - SCOPUS:85082857967
VL - 303
SP - 296
EP - 304
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
ER -
ID: 239808851