I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs

DOI10.1016/J.TCS.2014.10.043MaRDI QIDQ2339449zbMATH OpenOpenAlexFDO

Authors Alka Bhushan, G. Sajith

Publication date 1 April 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.10.043

zbMATH Keywords

external memory algorithmgraph algorithmI/O complexitylower boundminimum cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Randomized algorithms (68W20)

Recommendations

• I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs
• I/O-efficient shortest path algorithms for undirected graphs with random or bounded edge lengths
• scientific article; zbMATH DE number 177540
• scientific article; zbMATH DE number 1234600
• Approximation algorithms for minimum \(K\)-cut
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• An I/O efficient algorithm for minimum spanning trees
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• Iterative algorithms for generating minimal cutsets in directed graphs
• Practical performance of efficient minimum cut algorithms

Cites work

• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A matroid approach to finding edge connectivity and packing arborescences
• A simple and fast min-cut algorithm
• A simple min-cut algorithm
• An \NC Algorithm for Minimum Cuts
• Edge-Disjoint Spanning Trees of Finite Graphs
• External memory soft heap, and hard heap, a meldable priority queue
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Fully-dynamic min-cut
• scientific article; zbMATH DE number 1617242 (Why is no real title available?)
• scientific article; zbMATH DE number 437577 (Why is no real title available?)
• scientific article; zbMATH DE number 1305462 (Why is no real title available?)
• scientific article; zbMATH DE number 910869 (Why is no real title available?)
• scientific article; zbMATH DE number 910872 (Why is no real title available?)
• Maximal Flow Through a Network
• Minimum cuts in near-linear time
• The buffer tree: A technique for designing batched external data structures
• The maximum flow problem is log space complete for P

Cited in

(3)

• Cache oblivious minimum cut
• I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
• I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs

This page was built for publication: I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs

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