Mincut Sensitivity Data Structures for the Insertion of an Edge

DOI10.4230/LIPICS.ESA.2020.12MaRDI QIDQ5874478zbMATH OpenOpenAlexFDO

Authors Surender Baswana, S. K. Gupta, Till Knollmann

Publication date 7 February 2023

Full work available at URL https://doi.org/10.4230/LIPIcs.ESA.2020.12

zbMATH Keywords

data structuremincutsensitivity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Mincut sensitivity data structures for the insertion of an edge
• Approximating minimum cuts under insertions
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance
• scientific article; zbMATH DE number 6846417
• Incremental exact min-cut in polylogarithmic amortized update time

Cites work

• An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
• Fast and simple fully-dynamic cut tree construction
• Fully-dynamic min-cut
• Incremental exact min-cut in polylogarithmic amortized update time
• Maximal Flow Through a Network
• Multi-Terminal Network Flows
• On the structure of all minimum cuts in a network and applications
• The level ancestor problem simplified
• The Transitive Reduction of a Directed Graph
• Tight Bounds for Gomory-Hu-like Cut Counting
• Very Simple Methods for All Pairs Network Flow Analysis

Cited in

(2)

• Mincut sensitivity data structures for the insertion of an edge
• scientific article; zbMATH DE number 1263227 (Why is no real title available?)

This page was built for publication: Mincut Sensitivity Data Structures for the Insertion of an Edge

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