Unique lowest common ancestors in dags are almost as easy as matrix multiplication

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

We consider the problem of determining for each pair of vertices of a directed acyclic graph (dag) on n vertices whether or not it has a unique lowest common ancestor, and if so, finding such an ancestor. We show that this problem can be solved in time O(n ω logn), where ω< 2.376 is the exponent of the fastest known algorithm for multiplication of two n×n matrices.
We show also that the problem of determining a lowest common ancestor for each pair of vertices of an arbitrary dag on n vertices is solvable in time $widetilde{O}(n^2p+n^{omega})$ , where p is the minimum number of directed paths covering the vertices of the dag. With the help of random bits, we can solve the latter problem in time $widetilde{O}(n^2p)$ .

Details

Authors
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science
Original languageEnglish
Title of host publicationAlgorithms – ESA 2007 / Lecture Notes in Computer Science
PublisherSpringer
Pages265-274
Volume4698
ISBN (Print)978-3-540-75520-3
Publication statusPublished - 2007
Publication categoryResearch
Peer-reviewedYes
Event15th Annual European Symposium on Algorithms - Eilat, Israel
Duration: 2007 Oct 82007 Oct 10

Publication series

Name
Volume4698
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Annual European Symposium on Algorithms
CountryIsrael
CityEilat
Period2007/10/082007/10/10