MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Katriel, Irit
Bodlaender, Hans L.
dblp
dblp
Not MPG Author(s):
Bodlaender, Hans L.
Editor(s):
BibTeX cite key*:
SODATO2004
Title, Booktitle
Title*:
Online Topological Ordering
Booktitle*:
Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
Event, URLs
Conference URL::
Downloading URL:
http://www.mpi-sb.mpg.de/~irit/pub/TO.ps
Event Address*:
Vancouver, Canada
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
23 January 2005
Event End Date:
25 January 2005
Publisher
Name*:
SIAM
URL:
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
443-450
Year*:
2005
VG Wort Pages:
ISBN/ISSN:
0-89871-585-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
It is shown that the problem of maintaining the topological order
of the nodes of a directed acyclic graph
while inserting $m$ edges can be solved
in $O(\min\{m^{3/2}\log n,m^{3/2}+n^2\log n\})$ time, an
improvement over the best known result of $O(mn)$.
In addition, we analyze the complexity of the same algorithm with
respect to the treewidth $k$ of the underlying undirected graph. We show
that the algorithm runs in time $O(mk\log^2 n)$ for general $k$ and
that it can be implemented to run in $O(n\log n)$ time on trees, which
is optimal. If the input contains cycles, the algorithm detects this.
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{SODATO2004,
AUTHOR = {Katriel, Irit and Bodlaender, Hans L.},
TITLE = {Online Topological Ordering},
BOOKTITLE = {Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)},
PUBLISHER = {SIAM},
YEAR = {2005},
PAGES = {443--450},
ADDRESS = {Vancouver, Canada},
ISBN = {0-89871-585-7},
}


Entry last modified by Christine Kiesel, 04/25/2005
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)
Irit Katriel
Created
01/12/2005 01:54:22 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Irit Katriel
Irit Katriel
Edit Dates
25.04.2005 18:18:06
25.04.2005 17:45:22
25.04.2005 17:18:13
03/18/2005 03:22:03 PM
12.01.2005 13:54:22