Show simple item record

dc.contributor.authorDash, Santanu
dc.contributor.authorScholz, Sven-Bodo
dc.contributor.authorHerhut, Stephan
dc.contributor.authorChristianson, B.
dc.date.accessioned2013-11-21T12:22:17Z
dc.date.available2013-11-21T12:22:17Z
dc.date.issued2013-11
dc.identifier.citationDash , S , Scholz , S-B , Herhut , S & Christianson , B 2013 , ' A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ' , Theoretical Computer Science , vol. 513 , pp. 25-37 . https://doi.org/10.1016/j.tcs.2013.09.030
dc.identifier.issn0304-3975
dc.identifier.otherPURE: 2289623
dc.identifier.otherPURE UUID: 4a25b9bf-bfb1-4de7-92bc-56decf038d4b
dc.identifier.otherScopus: 84888136885
dc.identifier.urihttp://hdl.handle.net/2299/12152
dc.description.abstractLCA 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 DAGsen
dc.language.isoeng
dc.relation.ispartofTheoretical Computer Science
dc.rights/dk/atira/pure/core/openaccesspermission/open
dc.titleA scalable approach to computing representative lowest common ancestor in directed acyclic graphsen
dc.contributor.institutionSchool of Computer Science
dc.contributor.institutionScience & Technology Research Institute
dc.contributor.institutionCentre for Computer Science and Informatics Research
dc.description.statusPeer reviewed
dc.relation.schoolSchool of Computer Science
dc.description.versiontypeSubmitted Version
rioxxterms.versionSMUR
rioxxterms.versionofrecordhttps://doi.org/10.1016/j.tcs.2013.09.030
rioxxterms.typeJournal Article/Review
herts.preservation.rarelyaccessedtrue
herts.rights.accesstyperestrictedAccess


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record