A linear-time algorithm for finding a minimum spanning pseudoforest

1988/04/01 by Harold N. Gabow, Robert E. Tarjan · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Connected dominating set #Connectivity #Discrete mathematics #Graph #Interconnection Networks and Systems #Kruskal's algorithm #Mathematics #Minimum degree spanning tree #Minimum spanning tree #Reverse-delete algorithm #Spanning tree #Time complexity #VLSI and FPGA Design Techniques

paper · doi:10.1016/0020-0190(88)90089-0

crossref issued 1988/04/01 · crossref published 1988/04/01 · crossref published-print 1988/04/01 · openalex publication_date 1988/04/01 · crossref created 2002/07/26 · crossref deposited 2019/04/12 · openalex created_date 2025/10/10 · crossref indexed 2026/05/29 · openalex updated_date 2026/07/29

Citations

• Data Structures and Network Algorithms
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• A network flow solution to some nonlinear 0‐1 programming problems, with applications to graph theory
• Fibonacci heaps and their uses in improved network optimization algorithms
• Combinatorial optimization: networks and matroids

Cited by

• Pseudoforest [wikipedia]