A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem

DOI10.1007/3-540-59408-6_68zbMath1501.05030OpenAlexW1482549262MaRDI QIDQ5101432

Toshihide Ibaraki, Hiroshi Nagamochi

Publication date: 30 August 2022

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59408-6_68

zbMATH Keywords

\(k\)-edge-connectiontime augmentation algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Edge-connectivity augmentation problems
• Augmenting undirected connectivity in RNC and in randomized Õ(n³) time
• Efficient splitting off algorithms for graphs
• The minimum augmentation of any graph to aK-edge-connected graph
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• On sparse subgraphs preserving connectivity properties

This page was built for publication: A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem