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

DOI10.1007/3-540-56939-1_62zbMATH Open1418.68244OpenAlexW1593787329MaRDI QIDQ4630249FDOQ4630249

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

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

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)