Generalized cut trees for edge-connectivity

DOI10.1016/J.JCTB.2023.11.003MaRDI QIDQ6187342zbMATH OpenFDO

Authors On-Hei S. Lo, Jens M. Schmidt

Publication date 15 January 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCTB.2023.11.003

zbMATH Keywords

contraction-based sparsificationedge-connectivitypendant pair

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A cut tree representation for pendant pairs
• The tree of cuts and minimal \(k\)-connected graphs
• Compact cactus representations of all non-trivial min-cuts
• Extracting maximal information about sets of minimum cuts
• Graphs with largest number of minimum cuts

Cites work

• A simple min-cut algorithm
• An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
• Compact cactus representations of all non-trivial min-cuts
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Deterministic Edge Connectivity in Near-Linear Time
• Existenz gewisser Konfigurationen in n-gesättigten Graphen und in Graphen genügend großer Kantendichte
• Grad und lokaler Zusammenhang in endlichen Graphen
• scientific article; zbMATH DE number 878899 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• Kantendisjunkte Wege in Graphen
• Local flow partitioning for faster edge connectivity
• Minimum cuts in near-linear time
• On the number of small cut in a graph
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time

Cited in

(1)

• A cut tree representation for pendant pairs

This page was built for publication: Generalized cut trees for edge-connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187342)