@InProceedings{chiang:graph,
  author = {Yi-Jen Chiang and and Michael T. Goodrich and Edward F. Grove and
  Roberto Tamassia and Darren Erik Vengroff and Jeffrey Scott Vitter},
  title = {External-Memory Graph Algorithms (Extended Abstract)},
  booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
  (SODA~'95)},
  year = {1995},
  month = {January},
  pages = {139--149},
  URL = {ftp://cs.duke.edu/pub/jsv/Papers/CGG95.external_graph.ps.Z},
  keywords = {parallel I/O algorithm, graph algorithm, pario-bib},
  abstract = {We present a collection of new techniques for designing and
  analyzing efficient external-memory algorithms for graph problems and
  illustrate how these techniques can be applied to a wide variety of specific
  problems. Our results include: \begin{itemize} \item {\em
  Proximate-neighboring}. We present a simple method for deriving
  external-memory lower bounds via reductions from a problem we call the
  ``proximate neighbors'' problem. We use this technique to derive non-trivial
  lower bounds for such problems as list ranking, expression tree evaluation,
  and connected components. \item {\em PRAM simulation}. We give methods for
  efficiently simulating PRAM computations in external memory, even for some
  cases in which the PRAM algorithm is not work-optimal. We apply this to
  derive a number of optimal (and simple) external-memory graph algorithms.
  \item {\em Time-forward processing}. We present a general technique for
  evaluating circuits (or ``circuit-like'' computations) in external memory. We
  also use this in a deterministic list ranking algorithm. \item {\em
  Deterministic 3-coloring of a cycle}. We give several optimal methods for
  3-coloring a cycle, which can be used as a subroutine for finding large
  independent sets for list ranking. Our ideas go beyond a straightforward PRAM
  simulation, and may be of independent interest. \item {\em External
  depth-first search}. We discuss a method for performing depth first search
  and solving related problems efficiently in external memory. Our technique
  can be used in conjunction with ideas due to Ullman and Yannakakis in order
  to solve graph problems involving closed semi-ring computations even when
  their assumption that vertices fit in main memory does not hold.
  \end{itemize} \par Our techniques apply to a number of problems, including
  list ranking, which we discuss in detail, finding Euler tours,
  expression-tree evaluation, centroid decomposition of a tree, least-common
  ancestors, minimum spanning tree verification, connected and biconnected
  components, minimum spanning forest, ear decomposition, topological sorting,
  reachability, graph drawing, and visibility representation.}
}