Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A path cover technique for LCAs in dags

Kowaluk, Miroslaw ; Lingas, Andrzej LU and Nowak, Johannes (2008) 11th Scandinavian workshop on algorithm theory 5124. p.222-223
Abstract
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].
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Algorithm theory – SWAT 2008 / Lecture notes in computer science
editor
Gudmundsson, Joachim
volume
5124
pages
222 - 223
publisher
Springer
conference name
11th Scandinavian workshop on algorithm theory
conference location
Gothenburg, Sweden
conference dates
2008-07-02 - 2008-07-04
external identifiers
  • scopus:54249093441
ISSN
0302-9743
1611-3349
ISBN
978-3-540-69900-2
DOI
10.1007/978-3-540-69903-3_21
project
VR 2005-4085
language
English
LU publication?
yes
id
ba7f841a-1630-40b0-921d-9d36e28e247e (old id 1670463)
date added to LUP
2016-04-01 11:55:29
date last changed
2025-01-14 23:48:57
@inproceedings{ba7f841a-1630-40b0-921d-9d36e28e247e,
  abstract     = {{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.<br/><br>
<br/><br>
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       = {{Kowaluk, Miroslaw and Lingas, Andrzej and Nowak, Johannes}},
  booktitle    = {{Algorithm theory – SWAT 2008 / Lecture notes in computer science}},
  editor       = {{Gudmundsson, Joachim}},
  isbn         = {{978-3-540-69900-2}},
  issn         = {{0302-9743}},
  language     = {{eng}},
  pages        = {{222--223}},
  publisher    = {{Springer}},
  title        = {{A path cover technique for LCAs in dags}},
  url          = {{http://dx.doi.org/10.1007/978-3-540-69903-3_21}},
  doi          = {{10.1007/978-3-540-69903-3_21}},
  volume       = {{5124}},
  year         = {{2008}},
}