Generalized cut trees for edge-connectivity

DOI10.1016/j.jctb.2023.11.003zbMath1530.05106MaRDI QIDQ6187342

Jens M. Schmidt, On-Hei S. Lo

Publication date: 15 January 2024

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

zbMATH Keywords

edge-connectivitypendant paircontraction-based sparsification

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• On the number of small cut in a graph
• Compact cactus representations of all non-trivial min-cuts
• Existenz gewisser Konfigurationen in \(n\)-gesättigten Graphen und in Graphen genügend großer Kantendichte
• Grad und lokaler Zusammenhang in endlichen Graphen
• Kantendisjunkte Wege in Graphen
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A simple min-cut algorithm
• Local Flow Partitioning for Faster Edge Connectivity
• Deterministic Edge Connectivity in Near-Linear Time
• Unit Capacity Maxflow in Almost $m^{4/3}$ Time
• Minimum cuts in near-linear time

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