de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

An O(n^2.75) algorithm for online topological ordering

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43983

Ajwani,  Deepak
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44447

Friedrich,  Tobias
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45038

Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Ajwani, D., Friedrich, T., & Meyer, U. (2006). An O(n^2.75) algorithm for online topological ordering. In Algorithm theory - SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory (pp. 53-64). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-220E-D
Zusammenfassung
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.