Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section