A linear-time algorithm for finding a minimum spanning pseudoforest
From MaRDI portal
Publication:1098629
DOI10.1016/0020-0190(88)90089-0zbMath0637.68045OpenAlexW2083831615MaRDI QIDQ1098629
Harold N. Gabow, Robert Endre Tarjan
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(88)90089-0
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (12)
Linear-time algorithms for parametric minimum spanning tree problems on planar graphs ⋮ On the revealed preference analysis of stable aggregate matchings ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ Transportation Problem Allowing Sending and Bringing Back ⋮ Second-order properties of undirected graphs ⋮ On matroids and hierarchical graphs ⋮ Forests, frames, and games: Algorithms for matroid sums and applications ⋮ Hamiltonian triangulations and circumscribing polygons of disjoint line segments ⋮ A rooted-forest partition with uniform vertex demand ⋮ On matroids and hierarchical graphs ⋮ Aromatic Butcher series ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
Cites Work
- Linear algorithms for edge-coloring trees and unicyclic graphs
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Forests, frames, and games: Algorithms for matroid sums and applications
- Parallel concepts in graph theory
- The Algebraic Geometry of Motions of Bar-and-Body Frameworks
- A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
- Implementation and Analysis of Binomial Queue Algorithms
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A linear-time algorithm for finding a minimum spanning pseudoforest
