Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs

DOI10.1007/s00453-008-9178-yzbMath1187.05042OpenAlexW1972636981MaRDI QIDQ848841

Yoko Akiyama, Toshimasa Ishii, Hiroshi Nagamochi

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

edge-connectivityedge-splittingundirected graphconnectivity augmentation problemnode-to-area connectivitypolynomial time deterministic algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (1)

Augmenting edge-connectivity between vertex subsets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge-connectivity augmentation problems
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Covering symmetric supermodular functions by graphs
• Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
• 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
• Edge-Connectivity Augmentation with Partition Constraints
• An Analytical Solution of Vector Diffraction for Focusing Optical Systems
• Edge connectivity between nodes and node-subsets
• NA-EDGE-CONNECTIVITY AUGMENTATION PROBLEMS BY ADDING EDGES(<Special Issue>Network Design, Control and Optimization)
• Data Security Equals Graph Connectivity

This page was built for publication: Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs