scientific article; zbMATH DE number 437577

MaRDI QIDQ3140458zbMATH OpenFDO

Authors David W. Matula

Publication date 15 December 1993

zbMATH Keywords

adjacency searchapproximation algorithmedge connectivityminimum cut size

Mathematics Subject Classification ID

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

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

(26)

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

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)