Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands

DOI10.1007/978-3-642-20877-5_42MaRDI QIDQ3010423zbMATH OpenOpenAlexFDO

Authors Takuro Fukunaga

Publication date 1 July 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-20877-5_42

Mathematics Subject Classification ID

Internet topics (68M11) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximating minimum cost source location problems with local vertex-connectivity demands
• Minimum cost source location problem with local 3-vertex-connectivity requirements
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
• Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs
• The source location problem with local 3-vertex-connectivity requirements
• Source location problems considering vertex-connectivity and edge-connectivity simultaneously
• Approximate the lower-bounded connected facility location problem
• Approximation algorithms for connected facility location problems
• Local search approximation algorithms for the sum of squares facility location problems

Cites work

• A factor 2 approximation algorithm for the generalized Steiner network problem
• A Greedy Heuristic for the Set-Covering Problem
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• Approximation algorithms for combinatorial problems
• Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 5485590 (Why is no real title available?)
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• Locating sources to meet flow demands in undirected networks
• Minimizing a monotone concave function with laminar covering constraints
• Minimum cost source location problem with local 3-vertex-connectivity requirements
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• Minimum cost source location problems with flow requirements
• On the ratio of optimal integral and fractional covers
• Source location problems considering vertex-connectivity and edge-connectivity simultaneously
• The source location problem with local 3-vertex-connectivity requirements

Cited in

(11)

• 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 minimum cost source location problems with local vertex-connectivity demands
• The source location problem with local 3-vertex-connectivity requirements
• Minimum cost source location problems with flow requirements
• Approximating source location and star survivable network problems
• Minimum Cost Source Location Problems with Flow Requirements
• Approximating source location and star survivable network problems
• Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs
• Minimum cost source location problem with local 3-vertex-connectivity requirements
• Approximation for the minimum cost doubly resolving set problem

This page was built for publication: Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands

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