Escaping a Grid by Edge-Disjoint Paths | Algorithmica Skip to main content
Springer Nature Link
Log in

Escaping a Grid by Edge-Disjoint Paths

  • Published:
Algorithmica Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

We present a technique for designing external memory data structures that support batched operations I/ O efficiently. We show how the technique can be used to develop external versions of a search tree, a priority queue, and a segment tree, and give examples of how these structures can be used to develop I/ O-efficient algorithms. The developed algorithms are either extremely simple or straightforward generalizations of known internal memory algorithms—given the developed external data structures.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Systems, The University of Hong Kong, Pokfulam Road, Hong Kong. wtchan@csis.hku.hk, chin@csis.hku.hk, hfting@csis.hku.hk., HK

    Wun-Tat Chan, Francis Y. L. Chin & Hing-Fung Ting

Authors
  1. Wun-Tat Chan
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Francis Y. L. Chin
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Hing-Fung Ting
    View author publications

    You can also search for this author inPubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chan, WT., Chin, F.Y.L. & Ting, HF. Escaping a Grid by Edge-Disjoint Paths . Algorithmica 36, 343–359 (2003). https://doi.org/10.1007/s00453-003-1023-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-003-1023-8

Keywords