On network design problems: fixed cost flows and the covering steiner problem
From MaRDI portal
Publication:2944490
DOI10.1145/1077464.1077470zbMath1321.68021MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68M10: Network design and communication in computer systems
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
On fixed cost \(k\)-flow problems, The minimum vulnerability problem on specific graph classes, Finding paths with minimum shared edges, The minimum vulnerability problem, Approximating \(k\)-generalized connectivity via collapsing HSTs, Improved approximation algorithms for label cover problems, Combinatorial optimization in system configuration design, Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications, The minimum degree group Steiner problem, Approximability of capacitated network design, The Minimum Vulnerability Problem on Graphs, Network flow spanners, Resource allocation by means of project networks: Dominance results
