Average-Case Analysis of Online Topological Ordering

Simple item page
dc.creatorAjwani, Deepak
dc.creatorFriedrich, Tobias
dc.date2008-02-07
dc.date.accessioned2026-07-07T09:19:19Z
dc.date.available2026-07-07T09:19:19Z
dc.descriptionMany applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of online topological ordering algorithms. We prove an expected runtime of O(n^2 polylog(n)) under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). This is much less than the best known worst-case bound O(n^{2.75}) for this problem.
dc.description22 pages, long version of ISAAC'07 paper
dc.identifierhttps://arxiv.org/abs/0802.1059
dc.identifierhttp://arxiv.org/abs/0802.1059
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/154348
dc.subjectData Structures and Algorithms
dc.titleAverage-Case Analysis of Online Topological Ordering
dc.typetext

Files

Collections

arXiv