Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs

DOI10.1016/j.dam.2006.04.017zbMath1110.68102OpenAlexW2170837469MaRDI QIDQ860392

Toshimasa Ishii, Masayuki Hagiwara

Publication date: 9 January 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10252/100

zbMATH Keywords

undirected graphconnectivity augmentation problemnode-to-area connectivitypolynomial time deterministic algorithmlocal edge-connectivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

The Generalized Terminal Backup Problem ⋮ A New Approach to Splitting-Off ⋮ Edge-Connectivity Augmentations of Graphs and Hypergraphs ⋮ Graph orientations with set connectivity requirements ⋮ A unifying approach to splitting-off ⋮ Augmenting edge-connectivity between vertex subsets ⋮ Covering symmetric semi-monotone functions ⋮ Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs ⋮ Covering skew-supermodular functions by hypergraphs of minimum total size

Cites Work

• Unnamed Item
• Unnamed Item
• Graph connectivity and its augmentation: Applications of MA orderings
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Hypergraph connectivity augmentation
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• Locating Sources to Meet Flow Demands in Undirected Networks
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• Edge connectivity between nodes and node-subsets