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

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

Hiroshi Nagamochi, Hiro Ito, Toshimasa Ishii

Publication date: 25 July 2002

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

zbMATH Keywords

digraph; undirected graph

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

Related Items

Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs, Multi-commodity Source Location Problems and Price of Greed, 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, A note on two source location problems, Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs, The source location problem with local 3-vertex-connectivity requirements, Minimum cost source location problems with flow requirements, Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three

Cites Work

• Unnamed Item
• 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
• Computing Vertex Connectivity: New Bounds from Old Techniques