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 a least log (superscript i) n for some constant i.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA194029

Entities

People

  • Harold N. Gabow
  • Robert Tarjan

Organizations

  • Princeton University

Tags

DTIC Thesaurus Topics

  • Algebraic Geometry
  • Algorithms
  • Computer Programming
  • Computer Science
  • Computers
  • Geometry
  • Graph Theory
  • Linear Programming
  • Lists (Data Structures)
  • New York
  • Optimization
  • Parallel Computing
  • Parallel Processing
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.