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

DOI10.1016/j.tcs.2014.10.043zbMath1315.68144OpenAlexW2108852404MaRDI QIDQ2339449

G. Sajith, Alka Bhushan

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

graph algorithmminimum cutlower boundI/O complexityexternal memory algorithm

Mathematics Subject Classification ID

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

Related Items

Cache Oblivious Minimum Cut

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fully-dynamic min-cut
• The maximum flow problem is log space complete for P
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• The buffer tree: A technique for designing batched external data structures
• A matroid approach to finding edge connectivity and packing arborescences
• A simple and fast min-cut algorithm
• External Memory Soft Heap, and Hard Heap, a Meldable Priority Queue
• Maximal Flow Through a Network
• Edge-Disjoint Spanning Trees of Finite Graphs
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• An $\NC$ Algorithm for Minimum Cuts
• A simple min-cut algorithm
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Minimum cuts in near-linear time