A scalable approach to computing representative lowest common ancestor in directed acyclic graphs

Santanu Dash, Sven-Bodo Scholz, Stephan Herhut, B. Christianson

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
1231 Downloads (Pure)

Abstract

LCA computation for vertex pairs in trees can be achieved in constant time after linear-time preprocessing. However, extension of these techniques to compute LCA for vertex-pairs in DAGs has been not possible due to the non-tree edges in a DAG. In this paper, we present an algorithm for computing the LCA for vertex pairs in a DAG which treats the DAGʼs spanning tree and its non-tree edges separately. Our approach enables us to tap the efficiency of existing LCA algorithms for trees. Furthermore, our algorithm decomposes the DAG into a set of component trees called clusters which significantly reduces the preprocessing necessary to incorporate non-tree edges in the LCA computation. Our algorithm seamlessly interpolates the performance graph between the best reported algorithms for trees and the best reported algorithms for DAGs depending on the incidence of non-tree edges in the DAG. Using the proposed techniques, it is possible to achieve near-linear preprocessing and constant query time for sparse DAGs
Original languageEnglish
Pages (from-to)25-37
JournalTheoretical Computer Science
Volume513
Early online date8 Oct 2013
DOIs
Publication statusPublished - Nov 2013

Fingerprint

Dive into the research topics of 'A scalable approach to computing representative lowest common ancestor in directed acyclic graphs'. Together they form a unique fingerprint.

Cite this