scientific article; zbMATH DE number 6846417

DOI10.4230/LIPICS.ESA.2016.46MaRDI QIDQ4606317zbMATH OpenFDO

Authors Gramoz Goranci, Mikkel Thorup, Monika R. Henzinger

Publication date 2 March 2018

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2016.46

zbMATH Keywords

dynamic graph algorithmsedge connectivityminimum cut

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Incremental exact min-cut in polylogarithmic amortized update time
• Deterministic mincut in almost-linear time
• scientific article; zbMATH DE number 1256718
• scientific article; zbMATH DE number 1256719
• Incremental algorithm for minimum cut and edge connectivity in hypergraph
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Approximating minimum cuts under insertions
• Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time
• scientific article; zbMATH DE number 7759280
• Approximation algorithms for minimum \(K\)-cut

Cited in

(6)

• Mincut sensitivity data structures for the insertion of an edge
• Incremental algorithm for minimum cut and edge connectivity in hypergraph
• Incremental exact min-cut in polylogarithmic amortized update time
• Approximating minimum cuts under insertions
• Density independent algorithms for sparsifying k-step random walks
• Mincut Sensitivity Data Structures for the Insertion of an Edge

This page was built for publication:

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