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

DOI10.1145/1077464.1077470MaRDI QIDQ2944490zbMATH OpenOpenAlexFDO

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

approximationflowgraphsoptimization

Mathematics Subject Classification ID

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

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

(23)

• Combinatorial optimization in system configuration design
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• Complexity of minimum irreducible infeasible subsystem covers for flow networks
• The minimum degree group Steiner problem
• Approximability of capacitated network design
• On fixed cost k-flow problems
• The minimum vulnerability problem on graphs
• Network design with coverage costs
• On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem
• Network flow spanners
• Resource allocation by means of project networks: dominance results
• 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
• Single-sink fractionally subadditive network design
• A min-edge cost flow framework for capacitated covering problems
• Models for a Steiner ring network design problem with revenues
• Improved approximation algorithms for label cover problems
• Adaptive-adversary-robust algorithms via small copy tree embeddings
• From directed Steiner tree to directed polymatroid Steiner tree in planar graphs
• Approximation algorithms for the generalized point-to-point 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)