A minimum spanning tree algorithm with inverse-ackermann type complexity

Research output: Contribution to journalArticle

186 Scopus citations

Abstract

A deterministic algorithm for computing a minimum spanning tree of a connected graph is presented. Its running time is O(m α (m, n)), where α is the classical functional inverse of Ackermann's function and n (respectively, m) is the number of vertices (respectively, edges). The algorithm is comparison-based: it uses pointers, not arrays, and it makes no numeric assumptions on the edge costs.

Original languageEnglish (US)
Pages (from-to)1028-1047
Number of pages20
JournalJournal of the ACM
Volume47
Issue number6
DOIs
StatePublished - Jan 1 2000

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Graphs
  • Matroids
  • Minimum spanning trees

Fingerprint Dive into the research topics of 'A minimum spanning tree algorithm with inverse-ackermann type complexity'. Together they form a unique fingerprint.

  • Cite this