A path cover technique for LCAs in dags

Summary, in English

As a second major result we show how to combine the path cover technique with LCA solutions for dags with small depth [9]. Our algorithm attains the best known upper time bound for this problem of O(n 2.575). However, most notably, the algorithm performs better on a vast amount of input dags, i.e. dags that do not have an almost linear-sized subdag of extremely regular structure.



Finally, we apply our technique to improve the general upper time bounds on the worst case time complexity for the problem of reporting LCAs for each triple of vertices recently established by Yuster[26].

• Author: Miroslaw Kowaluk; Andrzej Lingas; Johannes Nowak
• Editor: Joachim Gudmundsson
• Department/s: Computer Science
• Publishing year: 2008
• Language: English
• Pages: 222-223
• Publication/Series: Algorithm theory – SWAT 2008 / Lecture notes in computer science
• Volume: 5124
• Links: http://dx.doi.org/10.1007/978-3-540-69903-3_21
• Document type: Conference paper
• Publisher: Springer
• Topic: Computer Science
• Conference name: 11th Scandinavian workshop on algorithm theory
• Conference date: 2008-07-02 - 2008-07-04
• Conference place: Gothenburg, Sweden
• Status: Published
• Project: VR 2005-4085
• ISBN/ISSN/Other: ISSN: 1611-3349; ISSN: 0302-9743; ISBN: 978-3-540-69900-2