
Accession Number : ADA194029
Title : A LinearTime Algorithm for Finding a Minimum Spanning Pseudoforest,
Corporate Author : PRINCETON UNIV NJ DEPT OF COMPUTER SCIENCE
Personal Author(s) : Gabow, Harold N ; Tarjan, Robert E
PDF Url : ADA194029
Report Date : Jul 1987
Pagination or Media Count : 9
Abstract : A pseudoforest is a graph each of whose connected components is a tree or a tree plus an edge; a spanning pseudoforest of a graph contains the greatest number of edges possible. This paper shows that a minimum cost spanning pseudoforest of a graph with n vertices and m edges can be found in O(m + n) time. This implies that a minimum spanning tree can be found in O(m) time for graphs with girth a least log (superscript i) n for some constant i.
Descriptors : *GRAPHS, *ALGORITHMS, COSTS, EDGES, TIME, TREES, LINEARITY, LOW COSTS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE