On dynamic breadth-first search in external-memory

Conference object, Article, Preprint English OPEN
Meyer, Ulrich;
  • Publisher: IBFI Schloss Dagstuhl
  • Subject: Dynamic Graph Algorithms | Randomization | Computer Science - Data Structures and Algorithms | [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS] | BFS | ACM F.2.2 | External Memory
    • ddc: ddc:004
    arxiv: Computer Science::Data Structures and Algorithms
    acm: MathematicsofComputing_DISCRETEMATHEMATICS

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... View more
  • References (16)
    16 references, page 1 of 2

    [1] A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9), pages 1116-1127, 1988.

    [2] L. Arge, G. Brodal, and L. Toma. On external-memory MST, SSSP and multi-way planar graph separation. In Proc. 8th Scand. Workshop on Algorithmic Theory (SWAT), volume 1851 of LNCS, pages 433-447. Springer, 2000.

    [3] M. Atallah and U. Vishkin. Finding Euler tours in parallel. Journal of Computer and System Sciences, 29(30), pages 330-337, 1984.

    [4] A. Buchsbaum, M. Goldwasser, S. Venkatasubramanian, and J. Westbrook. On external memory graph traversal. In Proc. 11th Ann. Symposium on Discrete Algorithms (SODA), pages 859-860. ACM-SIAM, 2000.

    [5] Y. J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamasia, D. E. Vengroff, and J. S. Vitter. External memory graph algorithms. In Proc. 6th Ann.Symposium on Discrete Algorithms (SODA), pages 139- 149. ACM-SIAM, 1995.

    [6] T. H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.

    [7] C. Demetrescu, I. Finocchi, and A. Ribichini. Trading off space for passes in graph streaming problems. In 17th ACM-SIAM Symposium on Discrete Algorithms, pages 714-723, 2006.

    [8] D. Eppstein, Z. Galil, and G. Italiano. Dynamic graph algorithms. In Mikhail J. Atallah, editor, Algorithms and Theory of Computation Handbook, chapter 8. CRC Press, 1999.

    [9] E. Gal and S. Toledo. Algorithms and data structures for flash memories. ACM Computing Surveys, 37:138-163, 2005.

    [10] T. Hagerup and C. Ru¨b. A guided tour of chernoff bounds. Inf. Process. Lett., 33(6):305-308, 1990.

  • Similar Research Results (2)
  • Metrics
Share - Bookmark