Fast Augmenting Paths by Random Sampling from Residual Graphs
From MaRDI portal
Publication:5252688
DOI10.1137/070705994zbMath1314.05090OpenAlexW2146409551MaRDI QIDQ5252688
Matthew S. Levine, David R. Karger
Publication date: 2 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/97225
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Flows in graphs (05C21)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Random Sampling in Cut, Flow, and Network Design Problems
- Beyond the flow decomposition barrier
- Maximal Flow Through a Network
- An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
- Random sampling in residual graphs
- Multi-Terminal Network Flows
- Network Flow and Testing Graph Connectivity
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- A new approach to the minimum cut problem
- An Õ(n2) algorithm for minimum cuts
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- A new approach to computing maximum flows using electrical flows
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations