Efficient splitting off algorithms for graphs
From MaRDI portal
Publication:2817664
DOI10.1145/195058.195436zbMATH Open1345.05099OpenAlexW2148922672MaRDI QIDQ2817664FDOQ2817664
Authors: Harold N. Gabow 
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/195058.195436
Recommendations
- Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
- Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
- A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem
- scientific article; zbMATH DE number 1256720
- Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40)
Cited In (23)
- Recent results on well-balanced orientations
- Enumerating \(k\)-arc-connected orientations
- On the hardness of palletizing bins using FIFO queues
- A new contraction technique with applications to congruency-constrained cuts
- Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
- Well-balanced orientations of mixed graphs
- On orientations maximizing total arc-connectivity
- A New Approach to Splitting-Off
- Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
- Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
- Augmenting edge-connectivity between vertex subsets
- A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
- Title not available (Why is that?)
- Very cost effective bipartitions in graphs
- Simultaneous well-balanced orientations of graphs
- Multigraph augmentation under biconnectivity and general edge-connectivity requirements
- Graph connectivity and its augmentation: Applications of MA orderings
- Fast diameter computation within split graphs
- Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
- Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
- On 2-strong connectivity orientations of mixed graphs and related problems
- On element-connectivity preserving graph simplification
- A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem
This page was built for publication: Efficient splitting off algorithms for graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817664)
