Applications of Path Compression on Balanced Trees

Research output: Contribution to journalArticle

183 Scopus citations

Abstract

Several fast algorithms are presented for computing functions defined on paths in trees under various assumpuons. The algorithms are based on tree mampulatton methods first used to efficiently represent equivalence relations. The algorithms have [formula omitted] running tunes, where m and n are measures of the problem size and a Is a functional reverse of Ackermann's function By usmg one or more of these algorithms m combination with other techniques, it is possible to solve the followmg graph problems m O(ma(m, n)) tnne, where m Is the number of edges and n Is the number of vertices m the problem graph A Venfymg a minimum spanning tree m an undirected graph (Best previously known time bound O(m log log n).) B Flndmg dominators in a flow graph (Best previously known tune bound O(n log n + m).) C Solvmg a path problem on a reducible flow graph. (Best previously known time bound. O(m log n) ) Application A is discussed.

Original languageEnglish (US)
Pages (from-to)690-715
Number of pages26
JournalJournal of the ACM (JACM)
Volume26
Issue number4
DOIs
StatePublished - Oct 1 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • balanced tree
  • dominators
  • equivalence relation
  • global flow analysis
  • graph algorithm
  • minimum spanning tree
  • path compression
  • path problem
  • tree

Fingerprint Dive into the research topics of 'Applications of Path Compression on Balanced Trees'. Together they form a unique fingerprint.

  • Cite this