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

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

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)

• 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
• A New Approach to Splitting-Off
• On orientations maximizing total arc-connectivity
• 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
• Very cost effective bipartitions in graphs
• scientific article; zbMATH DE number 1953093 (Why is no real title available?)
• 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
• Splitting-off in hypergraphs
• Hypergraph connectivity augmentation in strongly polynomial time
• Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
• Splitting-off in hypergraphs
• Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
• On element-connectivity preserving graph simplification
• On 2-strong connectivity orientations of mixed graphs and related problems
• 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)