Approximating source location and star survivable network problems

DOI10.1016/J.TCS.2017.02.008MaRDI QIDQ528470zbMATH OpenOpenAlexFDO

Authors Guy Kortsarz, Zeev Nutov

Publication date 12 May 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2017.02.008

zbMATH Keywords

source locationsubmodular coversurvivable network

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Programming involving graphs or networks (90C35)

Recommendations

• Approximating source location and star survivable network problems
• A note on two source location problems
• Minimum cost source location problems with flow requirements
• Minimum Cost Source Location Problems with Flow Requirements
• Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• Algorithmic Aspects of Graph Connectivity
• An algorithm for source location in directed graphs
• An analysis of the greedy algorithm for the submodular set covering problem
• An application of submodular flows
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Approximating minimum cost source location problems with local vertex-connectivity demands
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Approximating node-connectivity augmentation problems
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Generalized submodular cover problems and applications
• Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• Locating sources to meet flow demands in undirected networks
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• Minimum cost source location problems with flow requirements
• On sparse subgraphs preserving connectivity properties
• On the ratio of optimal integral and fractional covers
• Parameters of two-prover-one-round game and the hardness of connectivity problems
• Tight approximation algorithm for connectivity augmentation problems

Cited in

(4)

• Approximating \(k\)-connected \(m\)-dominating sets
• Approximating source location and star survivable network problems
• Approximating k-Connected m-Dominating Sets
• On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

This page was built for publication: Approximating source location and star survivable network problems

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