# The Library

### Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Tools

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.**

Official URL: http://dx.doi.org/10.1016/j.tcs.2007.02.053

## 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 |

Official 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

### Actions (login required)

View Item |