Average-Case Analysis of Online Topological Ordering

Details Average-Case Analysis of Online Topological Ordering Average-Case Analysis of Online Topological Ordering

2008-02-07

arxiv.org/abs/0802.1059v1

Computer Science

Data Structures and Algorithms

22 pages, long version of ISAAC'07 paper

Scientific paper

Many 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.

Affiliated with

Also associated with

No associations

Rating

Average-Case Analysis of Online Topological Ordering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Average-Case Analysis of Online Topological Ordering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Average-Case Analysis of Online Topological Ordering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-507888