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

DOI10.1007/978-3-540-77120-3_5zbMath1193.68195OpenAlexW1541319718MaRDI QIDQ5387743

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum cost source location problem with local 3-vertex-connectivity requirements
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Some APX-completeness results for cubic graphs
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• An algorithm for source location in directed graphs
• The source location problem with local 3-vertex-connectivity requirements
• Locating Sources to Meet Flow Demands in Undirected Networks
• Minimum Cost Source Location Problems with Flow Requirements
• Network Flow and Testing Graph Connectivity
• Source location problems considering vertex-connectivity and edge-connectivity simultaneously
• Transversals of subtree hypergraphs and the source location problem in digraphs

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