Compact cactus representations of all non-trivial min-cuts
In: Discrete Applied Mathematics, Jg. 303 (2021-11-01), S. 296-304
Online
unknown
Zugriff:
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 $\tilde{O}(n/\delta)$ vertices and $\tilde{O}(n)$ edges that preserves all non-trivial min-cuts of $G$, where $\delta$ is the minimum degree of $G$ and $\tilde{O}$ 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/\delta)$ vertices and $O(n)$ edges, preserves all non-trivial min-cuts and can be computed in near-linear time $\tilde{O}(m)$, where $m$ is the number of edges of $G$. We also obtain that every simple graph has $O((n/\delta)^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/\delta)$ 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 $\tilde{O}(m) + O(n^2 / \delta)$ time for every simple graph, which improves the previous best time bound $O(nm)$ given by Gusfield and Naor.
Comment: 12 pages, 3 figures
Titel: |
Compact cactus representations of all non-trivial min-cuts
|
---|---|
Autor/in / Beteiligte Person: | On-Hei Solomon Lo ; Thorup, Mikkel ; Jens Ejbye Schmidt |
Link: | |
Zeitschrift: | Discrete Applied Mathematics, Jg. 303 (2021-11-01), S. 296-304 |
Veröffentlichung: | Elsevier BV, 2021 |
Medientyp: | unknown |
ISSN: | 0166-218X (print) |
DOI: | 10.1016/j.dam.2020.03.046 |
Schlagwort: |
|
Sonstiges: |
|