Can I read Space-Efficient Implementations of Graph Search Methods on EtoBox?

Space-Efficient Implementations of Graph Search Methods by Robert E. Tarjan is a Computer Science article available to read on EtoBox.

What is Space-Efficient Implementations of Graph Search Methods about?

Several space-efficmnt implementations of the two most common and useful kinds of graph search, namely, breadth-first search and depth-first search, are discussed. A straightforward implementation of each method requires n bits and n + O(1) pointers of auxiliary storage, where n is the number of vertices in the graph. We devise methods that need only 2n + m bits, of which m are read-only, where rn is the number of edges in the graph. We save space by folding the queue or stack required by the search into the graph representation; two of our methods for depth-first search are variants of the Deutsch-Schorr-Waite list-marking algorithm. Our algorithms are expressed in a version of Dijkstra's guarded command language.

Who reads Space-Efficient Implementations of Graph Search Methods?

Author

Robert E. Tarjan

Publisher

Association for Computing Machinery; Association for Computing Machinery (ACM) (ISSN 0098-3500)

Published

1983

Language

EN

Field

Computer Science (Physical Sciences)