Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Online Topological Ordering

Katriel, I., & Bodlaender, H. L. (2005). Online Topological Ordering. In Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05) (pp. 443-450). Philadelphia, USA: SIAM.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2730-8 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2731-6
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Katriel, Irit1, Autor           
Bodlaender, Hans L., Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2005-04-252005
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: Philadelphia, USA : SIAM
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 279191
Anderer: Local-ID: C1256428004B93B8-BF8C20579797338CC1256F870046E540-SODATO2004
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Vancouver, Canada
Start-/Enddatum: 2005-01-23

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Philadelphia, USA : SIAM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 443 - 450 Identifikator: ISBN: 0-89871-585-7