Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs

DOI10.1007/978-3-540-77120-3_5MaRDI QIDQ5387743zbMATH OpenOpenAlexFDO

Authors Toshimasa Ishii

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://barrel.repo.nii.ac.jp/?action=repository_action_common_download&item_id=2614&item_no=1&attribute_id=19&file_no=1

Mathematics Subject Classification ID

Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
• Approximating minimum cost source location problems with local vertex-connectivity demands
• 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 problems with flow requirements

Cites work

• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• An algorithm for source location in directed graphs
• scientific article; zbMATH DE number 2152473 (Why is no real title available?)
• scientific article; zbMATH DE number 956792 (Why is no real title available?)
• Locating sources to meet flow demands in undirected networks
• 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
• Network Flow and Testing Graph Connectivity
• Some APX-completeness results for cubic graphs
• Source location problems considering vertex-connectivity and edge-connectivity simultaneously
• The source location problem with local 3-vertex-connectivity requirements
• Transversals of subtree hypergraphs and the source location problem in digraphs

Cited in

(5)

• Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
• Approximating minimum cost source location problems with local vertex-connectivity demands
• On the multicriterial problem of the search for optimal sources in a graph
• Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands
• Multi-commodity Source Location Problems and Price of Greed

This page was built for publication: Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs

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