### 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

## Fingerprint Dive into the research topics of 'A linear-time algorithm for finding a minimum spanning pseudoforest'. Together they form a unique fingerprint.

## Cite this

Gabow, H. N., & Tarjan, R. E. (1988). A linear-time algorithm for finding a minimum spanning pseudoforest.

*Information Processing Letters*,*27*(5), 259-263. https://doi.org/10.1016/0020-0190(88)90089-0