de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Online Topological Ordering

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44744

Katriel,  Irit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

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.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2730-8
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.