On Element-Connectivity Preserving Graph Simplification

DOI10.1007/978-3-662-48350-3_27zbMath1466.68056OpenAlexW2276245879MaRDI QIDQ3452796

Chandra Chekuri, Thapanapong Rukkanchanunt, Chao Xu

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48350-3_27

zbMATH Keywords

reductionbisubmodularityGomory-Hu treeelement-connectivity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The \(\kappa_k\)-connectivity of line graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Network design via iterative rounding of setpair relaxations
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Efficient splitting off algorithms for graphs
• Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
• A Graph Reduction Step Preserving Element-Connectivity and Packing Steiner Trees and Forests
• An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
• Algorithms for two bottleneck optimization problems
• Network Flow and Testing Graph Connectivity
• On some connectivity properties of Eulerian graphs
• A Reduction Method for Edge-Connectivity in Graphs
• On sparse subgraphs preserving connectivity properties
• Counterexamples for Directed and Node Capacitated Cut-Trees
• Computing Vertex Connectivity: New Bounds from Old Techniques
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Graph Connectivities, Network Coding, and Expander Graphs
• Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-Connectivities