Multigraph augmentation under biconnectivity and general edge-connectivity requirements
From MaRDI portal
Publication:2719846
DOI10.1002/net.4zbMath0974.05048MaRDI QIDQ2719846
Toshihide Ibaraki, Hiroshi Nagamochi, Toshimasa Ishii
Publication date: 19 December 2001
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://barrel.repo.nii.ac.jp/?action=repository_uri&item_id=64
augmentation; edge-connectivity; vertex-connectivity; polynomial deterministic algorithm; undirected multigraph
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Edge-connectivity augmentation problems
- A minimum 3-connectivity augmentation of a graph
- Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
- A note on the vertex-connectivity augmentation problem
- On the optimal vertex-connectivity augmentation
- A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
- Optimal augmentation of a 2-vertex-connected multigraph to an \(\ell\)-edge-connected and 3-vertex-connected multigraph
- Efficient splitting off algorithms for graphs
- Finding a Smallest Augmentation to Biconnect a Graph
- A new approach to the maximum-flow problem
- The minimum augmentation of any graph to aK-edge-connected graph
- Multi-Terminal Network Flows
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Augmentation Problems
- A Reduction Method for Edge-Connectivity in Graphs
- Edge-Connectivity Augmentation Preserving Simplicity
- Data Security Equals Graph Connectivity
- Augmenting Outerplanar Graphs
- Depth-First Search and Linear Graph Algorithms