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.
Original language | English (US) |
---|---|
Pages (from-to) | 259-263 |
Number of pages | 5 |
Journal | Information Processing Letters |
Volume | 27 |
Issue number | 5 |
DOIs | |
State | Published - Apr 28 1988 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
Keywords
- Minimum spanning tree
- girth
- graph
- pseudoforest