Deterministic O(nm) time edge-splitting in undirected graphs
From MaRDI portal
Publication:1383804
DOI10.1023/A:1009739202898zbMATH Open0895.90172OpenAlexW1483203801MaRDI QIDQ1383804FDOQ1383804
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
Recommendations
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
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)
