Improved Fully Dynamic Reachability Algorithm for Directed Graph

Details Improved Fully Dynamic Reachability Algorithm for Directed Graph Improved Fully Dynamic Reachability Algorithm for Directed Graph

2007-11-21

arxiv.org/abs/0711.3250v1

Computer Science

Data Structures and Algorithms

Scientific paper

We propose a fully dynamic algorithm for maintaining reachability information in directed graphs. The proposed deterministic dynamic algorithm has an update time of $O((ins*n^{2}) + (del * (m+n*log(n))))$ where $m$ is the current number of edges, $n$ is the number of vertices in the graph, $ins$ is the number of edge insertions and $del$ is the number of edge deletions. Each query can be answered in O(1) time after each update. The proposed algorithm combines existing fully dynamic reachability algorithm with well known witness counting technique to improve efficiency of maintaining reachability information when edges are deleted. The proposed algorithm improves by a factor of $O(\frac{n^2}{m+n*log(n)})$ for edge deletion over the best existing fully dynamic algorithm for maintaining reachability information.

Affiliated with

Also associated with

No associations

Rating

Improved Fully Dynamic Reachability Algorithm for Directed Graph 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 Improved Fully Dynamic Reachability Algorithm for Directed Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Fully Dynamic Reachability Algorithm for Directed Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-413772