1979/10/01 by Robert E. Tarjan · 3 citations
Computer Science · Mathematics · #Advanced Database Systems and Queries #Algorithms and Data Compression #Formal Methods in Verification #Citation #Computer science #Path (computing) #Information retrieval #Operations research #Library science #Mathematics #Operating system
paper · pdf · doi:10.1145/322154.322161
openalex publication_date 1979/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/21
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 O((m + n)a(m + n, n)) 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) )