On Dynamic Breadth-First Search in External-Memory

Details On Dynamic Breadth-First Search in External-Memory On Dynamic Breadth-First Search in External-Memory

2008-02-20

arxiv.org/abs/0802.2847v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Data Structures and Algorithms

Scientific paper

We provide the first non-trivial result on dynamic breadth-first search (BFS) in external-memory: For general sparse undirected graphs of initially $n$ nodes and O(n) edges and monotone update sequences of either $\Theta(n)$ edge insertions or $\Theta(n)$ edge deletions, we prove an amortized high-probability bound of $O(n/B^{2/3}+\sort(n)\cdot \log B)$ I/Os per update. In contrast, the currently best approach for static BFS on sparse undirected graphs requires $\Omega(n/B^{1/2}+\sort(n))$ I/Os.

Affiliated with

Also associated with

No associations

Rating

On Dynamic Breadth-First Search in External-Memory 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 On Dynamic Breadth-First Search in External-Memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Dynamic Breadth-First Search in External-Memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647816