English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

MPS-Authors
/persons/resource/persons43983

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

/persons/resource/persons44447

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

/persons/resource/persons45038

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


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