scientific article; zbMATH DE number 437577

MaRDI QIDQ3140458zbMATH OpenFDO

Authors David W. Matula

Publication date 15 December 1993

zbMATH Keywords

approximation algorithmedge connectivityadjacency searchminimum cut size

Mathematics Subject Classification ID

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

Recommendations

• Deterministic Edge Connectivity in Near-Linear Time
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• Distributed edge connectivity in sublinear time
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Efficient algorithms for computing all low \(s\)-\(t\) edge connectivities and related problems

Cited in

(23)

• Computing weighted strength and applications to partitioning
• Practical minimum cut algorithms
• Greedy splitting algorithms for approximating multiway partition problems
• Efficient algorithms for computing all low \(s\)-\(t\) edge connectivities and related problems
• Approximating minimum cuts under insertions
• Minimum cuts and sparsification in hypergraphs
• Local flow partitioning for faster edge connectivity
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs
• Breaking quadratic time for small vertex connectivity and an approximation scheme
• A linear time algorithm for computing 3-edge-connected components in a multigraph
• Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness
• Minimum Cuts of Simple Graphs in Almost Always Linear Time
• Minimum cut in \(O(m \log^2 n)\) time
• An improved linear edge bound for graph linkages
• Graph connectivity and its augmentation: Applications of MA orderings
• Distributed edge connectivity in sublinear time
• Connectivity algorithms
• Finding the edge connectivity of directed graphs
• Fast and Deterministic Approximations for k-Cut.
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Deterministic Edge Connectivity in Near-Linear Time
• Fast and deterministic approximations for \(k\)-cut

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 Q3140458)