Efficient splitting off algorithms for graphs

DOI10.1145/195058.195436MaRDI QIDQ2817664zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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 O(nm) time edge-splitting in undirected graphs

Cited in

(26)

• Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
• Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems
• A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
• Fast diameter computation within split graphs
• Enumerating \(k\)-arc-connected orientations
• On the hardness of palletizing bins using FIFO queues
• Simultaneous well-balanced orientations of graphs
• Multigraph augmentation under biconnectivity and general edge-connectivity requirements
• Very cost effective bipartitions in graphs
• On element-connectivity preserving graph simplification
• A New Approach to Splitting-Off
• scientific article; zbMATH DE number 1953093 (Why is no real title available?)
• Augmenting edge-connectivity between vertex subsets
• A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem
• Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
• Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
• A new contraction technique with applications to congruency-constrained cuts
• On orientations maximizing total arc-connectivity
• Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
• On 2-strong connectivity orientations of mixed graphs and related problems
• Splitting-off in hypergraphs
• Splitting-off in hypergraphs
• Graph connectivity and its augmentation: Applications of MA orderings
• Hypergraph connectivity augmentation in strongly polynomial time
• Recent results on well-balanced orientations
• Well-balanced orientations of mixed graphs

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)