Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
From MaRDI portal
Publication:5252687
DOI10.1137/070705970zbMath1314.05089arXivcs/0207078OpenAlexW1543491698MaRDI QIDQ5252687
David R. Karger, András A. Benczúr
Publication date: 2 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0207078
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
Minimum Cuts and Sparsification in Hypergraphs, Unnamed Item, Faster cut sparsification of weighted graphs, Models and methods for solving the problem of network vulnerability, Refined Vertex Sparsifiers of Planar Graphs, Fixed parameter approximation scheme for min-max \(k\)-cut, A General Framework for Graph Sparsification, Fast Augmenting Paths by Random Sampling from Residual Graphs, Unnamed Item, Near-Optimal Distributed Maximum Flow, Sparsification of Two-Variable Valued Constraint Satisfaction Problems
Cites Work
- Unnamed Item
- 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
- Random sampling in cut, flow, and network design problems
- $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
- Beyond the flow decomposition barrier
- Maximal Flow Through a Network
- On clusterings
- A new approach to the maximum-flow problem
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- A new approach to the minimum cut problem
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Twice-Ramanujan Sparsifiers
- Fast Augmenting Paths by Random Sampling from Residual Graphs
- Probability Inequalities for Sums of Bounded Random Variables
- A general framework for graph sparsification
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
- Minimum cuts in near-linear time
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Graph Sparsification by Effective Resistances
