Deterministic O(nm) time edge-splitting in undirected graphs

DOI10.1023/A:1009739202898MaRDI QIDQ1383804zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Toshihide Ibaraki

Publication date 13 April 1998

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1009739202898

zbMATH Keywords

multigraphedge-splittingedge-connectivity augmentation problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 1256720
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem
• Augmenting Undirected Edge Connectivity in Õ(n2) Time

Cited in

(17)

• Efficient splitting off algorithms for graphs
• \(O(m\log n)\) split decomposition of strongly-connected graphs
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
• \(O(m \log n)\) split decomposition of strongly connected graphs
• Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
• Polyhedral structure of submodular and posi-modular systems
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• Multigraph augmentation under biconnectivity and general edge-connectivity requirements
• Graph connectivity and its augmentation: Applications of MA orderings
• Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
• Augmenting the connectivity of geometric graphs
• Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
• Fast edge orientation for unweighted graphs
• An improved approximation guarantee for prize-collecting TSP
• Augmenting the connectivity of outerplanar graphs
• A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem

This page was built for publication: Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs

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