Accession Number : ADA194029

Title :   A Linear-Time 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