LCA queries in directed acyclic graphs
(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:
https://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
- 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
- 2024-03-26 07:07:23
@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}},
}