Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
From MaRDI portal
Publication:4630249
DOI10.1007/3-540-56939-1_62zbMath1418.68244OpenAlexW1593787329MaRDI QIDQ4630249
Naveen Garg, Mihalis Yannakakis, Vijay V. Vazirani
Publication date: 29 March 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-56939-1_62
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Flows in graphs (05C21)
Related Items (3)
Multiway cuts in directed and node weighted graphs ⋮ On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints ⋮ Approximations for the disjoint paths problem in high-diameter planar networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- The ellipsoid method and its consequences in combinatorial optimization
- Optimization, approximation, and complexity classes
- An Algorithm for Determining Whether a Given Binary Matroid is Graphic
- An Almost Linear-Time Algorithm for Graph Realization
- A linear-time approximation algorithm for the weighted vertex cover problem
- On the multiway cut polyhedron
- Graph Theory and Integer Programming
- On the approximability of the maximum common subgraph problem
- On the hardness of approximating minimization problems
- Excluded minors, network decomposition, and multicommodity flow
- Improved bounds on the max-flow min-cut ratio for multicommodity flows
- Approximate max-flow min-(multi)cut theorems and their applications
- A primal-dual approximation algorithm for generalized Steiner network problems
- Maximum matching and a polyhedron with 0,1-vertices
This page was built for publication: Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
