A linear-time algorithm for finding a minimum spanning pseudoforest

Harold N. Gabow; Robert E. Tarjan

doi:10.1016/0020-0190(88)90089-0

A linear-time algorithm for finding a minimum spanning pseudoforest

Harold N. Gabow
, Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

18 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⁽ⁱ⁾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	https://doi.org/10.1016/0020-0190(88)90089-0
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

Access to Document

10.1016/0020-0190(88)90089-0

Cite this

@article{35afba8aabde47169afc9771d7a0d561,

title = "A linear-time algorithm for finding a minimum spanning pseudoforest",

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.",

keywords = "Minimum spanning tree, girth, graph, pseudoforest",

author = "Gabow, \{Harold N.\} and Tarjan, \{Robert E.\}",

year = "1988",

month = apr,

day = "28",

doi = "10.1016/0020-0190(88)90089-0",

language = "English (US)",

volume = "27",

pages = "259--263",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - A linear-time algorithm for finding a minimum spanning pseudoforest

AU - Gabow, Harold N.

AU - Tarjan, Robert E.

PY - 1988/4/28

Y1 - 1988/4/28

N2 - 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.

AB - 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.

KW - Minimum spanning tree

KW - girth

KW - graph

KW - pseudoforest

UR - https://www.scopus.com/pages/publications/0023998251

UR - https://www.scopus.com/pages/publications/0023998251#tab=citedBy

U2 - 10.1016/0020-0190(88)90089-0

DO - 10.1016/0020-0190(88)90089-0

M3 - Article

AN - SCOPUS:0023998251

SN - 0020-0190

VL - 27

SP - 259

EP - 263

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

A linear-time algorithm for finding a minimum spanning pseudoforest

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this