Minimum cost source location problem with vertex-connectivity requirements in digraphs

DOI10.1016/S0020-0190(01)00183-1zbMath1003.68110OpenAlexW2094140918MaRDI QIDQ1607133

Hiro Ito, Hiroshi Nagamochi, Toshimasa Ishii

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00183-1

zbMATH Keywords

digraphundirected graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (17)

Maximum-cover source location problems with objective edge-connectivity three ⋮ Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs ⋮ Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs ⋮ Minimum cost source location problem with local 3-vertex-connectivity requirements ⋮ Static and dynamic source locations in undirected networks ⋮ Approximating minimum cost source location problems with local vertex-connectivity demands ⋮ Leader localization in multi-agent systems subject to failure: a graph-theoretic approach ⋮ Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs ⋮ The source location problem with local 3-vertex-connectivity requirements ⋮ Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands ⋮ Approximating source location and star survivable network problems ⋮ Minimum cost source location problems with flow requirements ⋮ Multi-commodity Source Location Problems and Price of Greed ⋮ A note on two source location problems ⋮ Approximating Source Location and Star Survivable Network Problems ⋮ Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs ⋮ Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A weighted matroid intersection algorithm
• Matroid intersection algorithms
• Network Flow and Testing Graph Connectivity
• On sparse subgraphs preserving connectivity properties
• Edge connectivity between nodes and node-subsets
• Computing Vertex Connectivity: New Bounds from Old Techniques

This page was built for publication: Minimum cost source location problem with vertex-connectivity requirements in digraphs