The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

LCA queries in directed acyclic graphs

På svenska

Author

Summary, in English

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.

Department/s

  • Computer Science

Publishing year

2005

Language

English

Pages

241-248

Publication/Series

Automata, Languages and Programming / Lecture Notes in Computer Science

Volume

3580

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

32nd International Colloquium, ICALP 2005

Conference date

2005-07-11 - 2005-07-15

Conference place

Lisbon, Portugal

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 978-3-540-27580-0