A New Approach to Incremental Cycle Detection and Related Problems

Details A New Approach to Incremental Cycle Detection and Related Problems A New Approach to Incremental Cycle Detection and Related Problems

2011-12-04

arxiv.org/abs/1112.0784v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the problem of detecting a cycle in a directed graph that grows by arc insertions, and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one suited to sparse graphs, and the other to dense graphs. The former takes the minimum of O(m^{3/2}) and O(mn^{2/3}) time to insert m arcs into an n-vertex graph; the latter takes O(n^2 log(n)) time. Our sparse algorithm is considerably simpler than a previous O(m^{3/2})-time algorithm; it is also faster on graphs of sufficient density. The time bound of our dense algorithm beats the previously best time bound of O(n^{5/2}) for dense graphs. Our algorithms rely for their efficiency on topologically ordered vertex numberings; bounds on the size of the numbers give bound on running times.

Affiliated with

Also associated with

No associations

Rating

A New Approach to Incremental Cycle Detection and Related Problems 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 A New Approach to Incremental Cycle Detection and Related Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Approach to Incremental Cycle Detection and Related Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-388737