Advanced

LCA queries in directed acyclic graphs

Kowaluk, M and Lingas, Andrzej LU (2005) 32nd International Colloquium, ICALP 2005 3580. p.241-248
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 all-pairs 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 all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the all-pairs LCA problem in time O(n(2+) (1)/(4-w)), 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 all-pairs 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 all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the all-pairs LCA problem in time O(n(2+) (1)/(4-w)), where w = 2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known O(n(w+3)/(2)) time-bound for the general all-pairs LCA problem in dags. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Automata, Languages and Programming / Lecture Notes in Computer Science
volume
3580
pages
241 - 248
publisher
Springer
conference name
32nd International Colloquium, ICALP 2005
conference location
Lisbon, Portugal
conference dates
2005-07-11 - 2005-07-15
external identifiers
  • wos:000230880500020
  • scopus:26444478558
ISSN
1611-3349
0302-9743
ISBN
978-3-540-27580-0
DOI
10.1007/11523468
project
VR 2002-4049
language
English
LU publication?
yes
id
a6ff7a17-690d-40bf-bc23-620c37973f7b (old id 227065)
date added to LUP
2016-04-01 12:17:10
date last changed
2021-05-26 01:25:32
@inproceedings{a6ff7a17-690d-40bf-bc23-620c37973f7b,
  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 all-pairs 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 all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the all-pairs LCA problem in time O(n(2+) (1)/(4-w)), where w = 2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known O(n(w+3)/(2)) time-bound for the general all-pairs LCA problem in dags.},
  author       = {Kowaluk, M and Lingas, Andrzej},
  booktitle    = {Automata, Languages and Programming / Lecture Notes in Computer Science},
  isbn         = {978-3-540-27580-0},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {241--248},
  publisher    = {Springer},
  title        = {LCA queries in directed acyclic graphs},
  url          = {http://dx.doi.org/10.1007/11523468},
  doi          = {10.1007/11523468},
  volume       = {3580},
  year         = {2005},
}