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

DOI10.1145/1077464.1077470MaRDI QIDQ2944490zbMATHOpenAlexFDO

Authors 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

optimizationgraphsapproximationflow

Mathematics Subject Classification ID

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

Recommendations

• On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem
• scientific article; zbMATH DE number 1303557
• Approximation Algorithms for Directed Steiner Problems
• On fixed cost k-flow problems
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science

Cited in

(20)

• Approximating \(k\)-generalized connectivity via collapsing HSTs
• The minimum degree group Steiner problem
• Models for a Steiner ring network design problem with revenues
• A min-edge cost flow framework for capacitated covering problems
• On fixed cost \(k\)-flow problems
• Single-sink fractionally subadditive network design
• Approximability of capacitated network design
• The minimum vulnerability problem on graphs
• Combinatorial optimization in system configuration design
• The minimum vulnerability problem on specific graph classes
• The minimum vulnerability problem
• Resource allocation by means of project networks: dominance results
• Network flow spanners
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• Network design with coverage costs
• Improved approximation algorithms for label cover problems
• Finding paths with minimum shared edges
• On fixed cost \(k\)-flow problems
• Complexity of minimum irreducible infeasible subsystem covers for flow networks
• On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem

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

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