Multigraph augmentation under biconnectivity and general edge-connectivity requirements

DOI10.1002/NET.4MaRDI QIDQ2719846zbMATH OpenOpenAlexFDO

Authors Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki

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

zbMATH Keywords

augmentationedge-connectivitypolynomial deterministic algorithmundirected multigraphvertex-connectivity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1372654
• Mathematical Foundations of Computer Science 2003
• Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
• scientific article; zbMATH DE number 2080257
• Optimal augmentation of a 2-vertex-connected multigraph to an -edge-connected and 3-vertex-connected multigraph

Cites work

• A minimum 3-connectivity augmentation of a graph
• A new approach to the maximum-flow problem
• A note on the vertex-connectivity augmentation problem
• A Reduction Method for Edge-Connectivity in Graphs
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• Augmentation Problems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Augmenting Outerplanar Graphs
• Data Security Equals Graph Connectivity
• Depth-First Search and Linear Graph Algorithms
• Deterministic O(nm) time edge-splitting in undirected graphs
• Edge-Connectivity Augmentation Preserving Simplicity
• Edge-connectivity augmentation problems
• Efficient splitting off algorithms for graphs
• Finding a Smallest Augmentation to Biconnect a Graph
• scientific article; zbMATH DE number 1256642 (Why is no real title available?)
• scientific article; zbMATH DE number 1405799 (Why is no real title available?)
• Multi-Terminal Network Flows
• On the optimal vertex-connectivity augmentation
• Optimal augmentation of a 2-vertex-connected multigraph to an -edge-connected and 3-vertex-connected multigraph
• The minimum augmentation of any graph to aK-edge-connected graph

Cited in

(4)

• Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
• scientific article; zbMATH DE number 1372654 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2003
• Graph connectivity and its augmentation: Applications of MA orderings

This page was built for publication: Multigraph augmentation under biconnectivity and general edge-connectivity requirements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2719846)