On network design problems: fixed cost flows and the covering steiner problem

DOI10.1145/1077464.1077470zbMath1321.68021OpenAlexW2018511415MaRDI QIDQ2944490

Guy Even, Wolfgang Slany, Guy Kortsarz

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1077464.1077470

zbMATH Keywords

optimizationapproximationgraphsflow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (13)

The minimum vulnerability problem on specific graph classes ⋮ The Minimum Vulnerability Problem on Graphs ⋮ Finding paths with minimum shared edges ⋮ Improved approximation algorithms for label cover problems ⋮ Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications ⋮ The minimum vulnerability problem ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Network flow spanners ⋮ Combinatorial optimization in system configuration design ⋮ The minimum degree group Steiner problem ⋮ Resource allocation by means of project networks: Dominance results ⋮ Approximability of capacitated network design ⋮ On fixed cost \(k\)-flow problems

This page was built for publication: On network design problems: fixed cost flows and the covering steiner problem