Fast Augmenting Paths by Random Sampling from Residual Graphs

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

zbMATH Keywords

minimum cutconnectivityrandom samplingnetwork reliabilitycut enumerationmaximum flow random graph

Mathematics Subject Classification ID

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

Unnamed Item, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs

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 Õ(n²) 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