MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Ajwani, Deepak
Friedrich, Tobias
Meyer, Ulrich
dblp
dblp
dblp
Editor(s):
Arge, Lars
Freivalds, Rusins
dblp
dblp
Not MPII Editor(s):
Arge, Lars
Freivalds, Rusins
BibTeX cite key*:
AFM06
Title, Booktitle
Title*:
An $O(n^2.75)$ algorithm for online topological ordering
Booktitle*:
Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory
Event, URLs
Conference URL::
http://www.lumii.lv/swat
Downloading URL:
Event Address*:
Riga, Latvia
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
6 July 2006
Event End Date:
8 July 2006
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4059
Number:
Month:
Pages:
53-64
Year*:
2006
VG Wort Pages:
29
ISBN/ISSN:
978-3-540-35753-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We present a simple algorithm which maintains the topological order of a directed acyclic graph with $n$ nodes under an online edge insertion sequence in $\O(n^{2.75})$ time, independent of the number of edges $m$ inserted. For dense DAGs, this is an improvement over the previous best result of $\O(\min\{m^{\frac{3}{2}} \log{n}, m^{\frac{3}{2}} + n^2 \log{n}\})$ by Katriel and Bodlaender. We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting.
Download
Access Level:
MPG

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
popular
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{AFM06,
AUTHOR = {Ajwani, Deepak and Friedrich, Tobias and Meyer, Ulrich},
EDITOR = {Arge, Lars and Freivalds, Rusins},
TITLE = {An ${O}(n^{2.75})$ algorithm for online topological ordering},
BOOKTITLE = {Algorithm theory - SWAT 2006 : 10th Scandinavian Workshop on Algorithm Theory},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4059},
PAGES = {53--64},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Riga, Latvia},
ISBN = {978-3-540-35753-7},
}


Entry last modified by Deepak Ajwani, 05/07/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Tobias Friedrich
Created
04/01/2006 03:27:58 PM
Revisions
13.
12.
11.
10.
9.
Editor(s)
Deepak Ajwani
Tobias Friedrich
Tobias Friedrich
Christine Kiesel
Christine Kiesel
Edit Dates
05/07/2007 02:19:26 PM
05/04/2007 07:07:17 PM
03/07/2007 04:26:42 PM
01.02.2007 08:43:18
12/08/2006 10:34:35 AM