A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest
Report ID: TR-108-87Author: Tarjan, Robert E. / Gabow, Harold N.
Date: 1987-07-00
Pages: 8
Download Formats: |PDF|
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 at least log(i)n for some constant i.