Approximating source location and star survivable network problems

DOI10.1016/J.TCS.2017.02.008zbMATH Open1378.90083OpenAlexW2589799731MaRDI QIDQ528470FDOQ528470

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

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

zbMATH Keywords

survivable networksource locationsubmodular cover

Mathematics Subject Classification ID

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

Cites Work

• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• An application of submodular flows
• On the ratio of optimal integral and fractional covers
• Generalized submodular cover problems and applications
• An analysis of the greedy algorithm for the submodular set covering problem
• Title not available (Why is that?)
• Algorithmic Aspects of Graph Connectivity
• On sparse subgraphs preserving connectivity properties
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Tight approximation algorithm for connectivity augmentation problems
• An algorithm for source location in directed graphs
• Locating sources to meet flow demands in undirected networks
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
• Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• Approximating node-connectivity augmentation problems
• Approximating minimum cost source location problems with local vertex-connectivity demands
• Minimum cost source location problems with flow requirements

Cited In (3)

• Approximating \(k\)-connected \(m\)-dominating sets
• 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)