Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover

DOI10.1007/3-540-56939-1_62MaRDI QIDQ4630249zbMATH OpenOpenAlexFDO

Authors Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

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

zbMATH Keywords

vertex coverintegral flowmulticommodity flowdistance labeledge capacity

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Flows in graphs (05C21)

Cites work

• scientific article; zbMATH DE number 4211829 (Why is no real title available?)
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 742977 (Why is no real title available?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• An Almost Linear-Time Algorithm for Graph Realization
• Approximate max-flow min-(multi)cut theorems and their applications
• Excluded minors, network decomposition, and multicommodity flow
• Graph Theory and Integer Programming
• Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• Maximum matching and a polyhedron with 0,1-vertices
• On the approximability of the maximum common subgraph problem
• On the hardness of approximating minimization problems
• On the multiway cut polyhedron
• Optimization, approximation, and complexity classes
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(4)

• On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
• Approximations for the disjoint paths problem in high-diameter planar networks
• Multiway cuts in directed and node weighted graphs
• Approximate max-flow min-multicut theorem for graphs of bounded treewidth

This page was built for publication: Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4630249)