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

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

2006-02-21

arxiv.org/abs/cs/0602073v2

Computer Science

Data Structures and Algorithms

20 pages, long version of SWAT'06 paper

Scientific paper

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^{3/2} log(n), m^{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. Our implementation outperforms them on certain hard instances while it is still competitive on random edge insertion sequences leading to complete DAGs.

Affiliated with

Also associated with

No associations

Rating

An O(n^{2.75}) algorithm for 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 An O(n^{2.75}) algorithm for online topological ordering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An O(n^{2.75}) algorithm for online topological ordering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-454092