Approximating minimum cuts under insertions

DOI10.1007/3-540-60084-1_81MaRDI QIDQ4645185zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• Incremental exact min-cut in polylogarithmic amortized update time
• scientific article; zbMATH DE number 6846417
• Fully-dynamic MIN-cut
• scientific article; zbMATH DE number 1003274

Cites work

• scientific article; zbMATH DE number 1003274 (Why is no real title available?)
• scientific article; zbMATH DE number 437577 (Why is no real title available?)
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• scientific article; zbMATH DE number 1263227 (Why is no real title available?)
• scientific article; zbMATH DE number 845842 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A data structure for dynamic trees
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
• Finding the Vertex Connectivity of Graphs
• Maintaining bridge-connected and biconnected components on-line
• Maintaining the 3-Edge-Connected Components of a Graph On-Line
• Network Flow and Testing Graph Connectivity
• Random sampling in cut, flow, and network design problems
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity

Cited in

(7)

• Fully-dynamic MIN-cut
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• scientific article; zbMATH DE number 6846417 (Why is no real title available?)
• Mincut Sensitivity Data Structures for the Insertion of an Edge
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance
• Incremental exact min-cut in polylogarithmic amortized update time
• Practical fully dynamic minimum cut algorithms

This page was built for publication: Approximating minimum cuts under insertions

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