Czumaj, Artur, Kowaluk, Miroslaw and Lingas, Andrzej. (2007) Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theoretical Computer Science, Vol.380 (No.1-2). pp. 37-46. ISSN 0304-3975

Full text not available from this repository.

Abstract

We present two new 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 0 (n m). 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 0 (n (2+lambda)), where A satisfies the equation to (1, lambda, I) = 1 + 2 lambda and w (1, lambda, 1) is the exponent of the multiplication of an n x n (lambda) matrix by an n (lambda) x n matrix. By the currently best known bounds on w 1, lambda, 1), the running time of our algorithm is O (n (2.575)). Our algorithm improves the previously known O (n (2.688)) time-bound for the general all-pairs LCA problem in dags by Bender et al. Our additional contribution is a faster algorithm for solving the all-pairs lowest common ancestor problem in dags of small depth, where the depth of a dag is defined as the length of the longest path in the dag. For all dags of depth at most h <= n alpha where alpha approximate to 0.294, our algorithm runs in a time that is asymptotically the same as that required for multiplying two n x n matrices, that is, O (n (w)); we also prove that this running time is optimal even for dags of depth 1. For dags with depth h > n (alpha) the running time of our algorithm is at most O (n (w) ho (0.468)). This algorithm is faster than our algorithm for arbitrary dags for all values of h <= n (0.42). (C) 2007 Elsevier B. V. All rights reserved.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Theoretical Computer Science
Publisher:	Elsevier Science BV
ISSN:	0304-3975
Date:	21 June 2007
Volume:	Vol.380
Number:	No.1-2
Number of Pages:	10
Page Range:	pp. 37-46
Identification Number:	10.1016/j.tcs.2007.02.053
Status:	Not Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Title of Event:	32nd International Colloquium on Automata, Languages and Programming (ICALP 2005)
Type of Event:	Other
Location of Event:	Lisbon, Portugal
Date(s) of Event:	July 11-15, 2005
URI:	http://wrap.warwick.ac.uk/id/eprint/31654

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item