A lower bound on the integrality gap for minimum multicut in directed networks
From MaRDI portal
Publication:705752
DOI10.1007/S00493-004-0031-XzbMATH Open1058.05033OpenAlexW1986291656MaRDI QIDQ705752FDOQ705752
Leonid Zosin, Michael Saks, Alex Samorodnitsky
Publication date: 14 February 2005
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-004-0031-x
Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Deterministic network models in operations research (90B10)
Cited In (7)
- On the Max-flow min-cut ratio for directed multicommodity flows
- Multicommodity flows and cuts in polymatroidal networks
- The all-or-nothing flow problem in directed graphs with symmetric demand pairs
- Approximating minimum feedback sets and multicuts in directed graphs
- An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
- Eliminating cycles in the discrete torus
- ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY
This page was built for publication: A lower bound on the integrality gap for minimum multicut in directed networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705752)
