LCA queries in directed acyclic graphs
(2005) 32nd International Colloquium, ICALP 2005 In Automata, Languages and Programming / Lecture Notes in Computer Science 3580. p.241248 Abstract
 We present two methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. The first method is surprisingly natural and solves the allpairs LCA problem for the input dag on n vertices and m edges in time O(nm). As a corollary, we obtain an O(n(2))time algorithm for finding genealogical distances considerably improving the previously known O(n (2.575)) timebound for this problem. The second method relies on a novel reduction of the allpairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the allpairs LCA problem in time O(n(2+) (1)/(4w)), where w = 2.376 is the exponent of the... (More)
 We present two methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. The first method is surprisingly natural and solves the allpairs LCA problem for the input dag on n vertices and m edges in time O(nm). As a corollary, we obtain an O(n(2))time algorithm for finding genealogical distances considerably improving the previously known O(n (2.575)) timebound for this problem. The second method relies on a novel reduction of the allpairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the allpairs LCA problem in time O(n(2+) (1)/(4w)), where w = 2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known O(n(w+3)/(2)) timebound for the general allpairs LCA problem in dags. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/227065
 author
 Kowaluk, M and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2005
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Automata, Languages and Programming / Lecture Notes in Computer Science
 volume
 3580
 pages
 241  248
 publisher
 Springer
 conference name
 32nd International Colloquium, ICALP 2005
 external identifiers

 wos:000230880500020
 scopus:26444478558
 ISSN
 16113349
 03029743
 ISBN
 9783540275800
 DOI
 10.1007/11523468
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 a6ff7a17690d40bfbc23620c37973f7b (old id 227065)
 date added to LUP
 20070816 14:07:45
 date last changed
 20180107 06:01:14
@inproceedings{a6ff7a17690d40bfbc23620c37973f7b, abstract = {We present two methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. The first method is surprisingly natural and solves the allpairs LCA problem for the input dag on n vertices and m edges in time O(nm). As a corollary, we obtain an O(n(2))time algorithm for finding genealogical distances considerably improving the previously known O(n (2.575)) timebound for this problem. The second method relies on a novel reduction of the allpairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the allpairs LCA problem in time O(n(2+) (1)/(4w)), where w = 2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known O(n(w+3)/(2)) timebound for the general allpairs LCA problem in dags.}, author = {Kowaluk, M and Lingas, Andrzej}, booktitle = {Automata, Languages and Programming / Lecture Notes in Computer Science}, isbn = {9783540275800}, issn = {16113349}, language = {eng}, pages = {241248}, publisher = {Springer}, title = {LCA queries in directed acyclic graphs}, url = {http://dx.doi.org/10.1007/11523468}, volume = {3580}, year = {2005}, }