Approximating minimum cuts under insertions

DOI10.1007/3-540-60084-1_81zbMath1412.68173OpenAlexW1584687374MaRDI QIDQ4645185

Monika R. Henzinger

Publication date: 10 January 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60084-1_81

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining bridge-connected and biconnected components on-line
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A data structure for dynamic trees
• Random sampling in cut, flow, and network design problems
• Finding the Vertex Connectivity of Graphs
• Maintaining the 3-Edge-Connected Components of a Graph On-Line
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
• Network Flow and Testing Graph Connectivity