A linear-time algorithm for finding a minimum spanning pseudoforest

Harold N. Gabow, Robert E. Tarjan

Research output: Contribution to journalArticle

13 Scopus citations

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 languageEnglish (US)
Pages (from-to)259-263
Number of pages5
JournalInformation Processing Letters
Volume27
Issue number5
DOIs
StatePublished - 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