1.
John H. Reif,
The Complexity of Extending a Graph Imbedding. Computer Science Department,
University of Rochester, TR-42, October 1978. [PDF]

2.
Ion
S. Filotti, Gary Miller, and John H. Reif, On Determining the
Genus of a Graph in 0(v^0(g)) Steps, *11th
Annual ACM Symposium on Theory of Computing(STOC79)*,
Atlanta, GA, April 1979, pp. 27-37. [PDF]

3.
John H. Reif,
Minimum s-t Cut of Planar Undirected Network in 0(n log^2n) Time, 8th
Colloquium on Automata, Languages and Programming, (Shimon Even and Oded Kariv, editors) volume 115
of Lecture Notes in Computer Science, pp. 56-67, Acre (Akko), Israel, 13-17
July 1981. Springer-Verlag. Published in *SIAM Journal on Computing*, Vol. 12, No.
1, February 1983, pp. 71-81. [PDF]

4.
John H. Reif
and Paul G. Spirakis, K-connectivity in Random
Undirected Graphs, *Discrete Mathematics*,* *Vol. 54, No. 2, April 1985, pp.
181-191. [PDF]

5.
John H. Reif
and Paul G. Spirakis, Strong k-connectivity in Digraphs
and Random Digraphs, Harvard University TR-25-81. [PDF]

6. John H. Reif and Paul G. Spirakis,
Expected Parallel Time and Sequential Space Complexity of Graph and Digraph
Problems, *Algorithmica*,
Special Issue on Graph Algorithms, Vol. 7, Numbers 5 & 7, pp. 597-630,
1992. [PDF]

7. John H. Reif and W.L. Scherlis,
Deriving Efficient Graph Algorithms. Logics of Programs
Workshop, Carnegie-Mellon University, Pittsburgh, PA, June 1983, Lecture Notes
in Computer Science, Vol. 164, 1984, pp. 421-441. Published in: Verification:
Theory and Practice: Essays Dedicated to Zohar Manna on the Occasion of His
64th Birthday (edited by Nachum Dershowitz), LNCS series Vol. 2772, pp. 645-681, 2004. [PDF]
or [PDF]

8. John H. Reif, Depth-First Search is Inherently
Sequential. *Information Processing
Letters*,* *Vol. 20, No. 5, June 12,
1985, pp. 229-234. [PDF]

9.
John H. Reif,
A Topological Approach to Dynamic Graph Connectivity. *Information Processing Letters*,*
*Vol. 25, No. 1, April 20, 1987, pp. 65-70. [PDF]

10.
Hristo Djidjev and John H. Reif, An Efficient Algorithm for the
Genus Problem with Explicit Construction of Forbidden Subgraphs.
*23rd Annual ACM Symposium on Theory of
Computing*, New Orleans, LA, May 1991, pp. 337-347. [PDF]

11.
Gary Miller
and John H. Reif, Parallel Tree Contraction and its Application. Harvard
University TR-18-85. *26th Annual IEEE
Symposium on Foundations of Computer Science*, Portland, OR, October 1985,
pp. 478-489.

a Portions Published as Parallel Tree Contraction
Part I: Fundamentals, Parallel Tree Contraction Part
1: Fundamentals. In Randomness and Computation, (*Advances in
Computing Research*, Vol. 5., Silvio
Micali, editor), pp. 47–72, JAI Press, Greenwich, Connecticut, 1989. [PDF]

b Portions Published as Parallel Tree Contraction
Part II: Further Applications, *SIAM
Journal on Computing*, Vol. 20, No. 6, pp. 1128-1147, December 1991. [PDF]

12.
Phlip Klein and John
H. Reif, An Efficient Parallel Algorithm for Planarity. *27th Annual IEEE Symposium on Foundations of Computer Science*,
Toronto, Canada, October 1986,* *pp.* *465-477. Published in *Journal of Computer and System Sciences*,* *Vol. 37, No. 2, October 1988, pp.
190-246. [PDF]

13.
Vijaya Ramachandran and John H. Reif, An Optimal Parallel
Algorithm for Graph Planarity. *30th
Annual IEEE Symposium on Foundations of Computer Science*, Research Triangle
Park, NC, October 1989, pp. 282-287. Published as Planarity
Testing in Parallel*, Journal of Computer and System Sciences*, **49**:3, December, 1994, pp. 517-561. [PostScript] [PDF]

14.
Victor Pan and
John H. Reif, The Parallel Computation of Minimum Cost Paths in Graphs by
Stream Contraction, *Information
Processing Letters*, Vol. 40, October 25,1991, pp. 79-83. [PDF]

15.
Victor Pan and
John H. Reif, Extension of the Parallel Nested Dissection Algorithm to Path
Algebra Problems. Presented at* 6th
Conference on Foundation of Software Technology and Theoretical Computer
Science*,* *New Delhi, India; *Lecture Notes in Computer Science*, Springer Verlag, Vol. 241,
pp. 470–487, 1986. An abstract of this paper appears as Parallel Nested
Dissection for Path Algebra Computations, *Operations
Research Letters*,* *Vol. 5, No. 4,
October 1986, pp. 177-184. [PDF] Published
as Fast and Efficient Solution of Path Algebra Problems, *Journal of Computer and Systems Sciences*, Vol. 38, No. 3, June
1989, pp. 494-510. [PDF]

16.
Hillel Gazit and John H. Reif, A Randomized Parallel Algorithm for
Planar Graph Isomorphism. *2nd Annual ACM
Symposium on Parallel Algorithms and Architectures*, Crete, Greece, July
1990, pp. 210-219. Published in* Journal
of Algorithms, *Vol. 28, No. 2, pp. 290-314, August 1998. [PostScript] [PDF]

17.
Yijie Han, Victor Pan,
and John H. Reif, Efficient Parallel Algorithms for Computing All Pair Shortest
Paths in Directed Graphs. University of Kentucky Technical Report 204-92. *4th Annual ACM Symposium on Parallel
Algorithms and Architectures*, San Diego, CA, July 1992, pp. 353-362.
Published in Algorithmica, Vol
17, pp. 399-415, 1997. [PDF]

18.
John H. Reif
and Steve R. Tate, Dynamic Algebraic Algorithms, *Proceedings of the* *5th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA'94),* TX, Jan. 1994.
pp.290-301. Published as On Dynamic Algorithms for Algebriac
Problems, Journal of Algorithms, 22(2):347-371,
February 1997. [PostScript]
[PDF]

19.
Joseph Cheriyan and John H. Reif, Parallel and Output Sensitive
Algorithms for Combinatorial and Linear Algebra Problems, 1992. *4th Annual ACM Symposium on Parallel
Algorithms and Architectures (SPAA'93*), Velon, Germany,
July 1993, p.50-56. Published as John H. Reif, Parallel Output Sensitive
Algorithms for Combinatorial and Linear Algebra Problems, *Journal of Computer and System Sciences*, Vol. 62, 2001, pp.
398-412. [PostScript]
[PDF]

20.
Sotiris
E. Nikoletseas, John H. Reif, Paul G. Spirakis, Moti Yung, Stochastic Graphs Have Short Memory: Fully
Dynamic Connectivity in Poly-Log Expected Time. *Proceedings of the 22nd Annual Colloquium on Automata, Languages and
Programming (ICALP'95)*, Szeged, Hungary, July 1995, pp. 159-170. [PDF]

21.
Joseph Cheriyan and John H. Reif, Algebraic Methods for Testing
the *k*-Vertex Connectivity of Directed
Graphs, *3rd Annual ACM-SIAM Symposium on
Discrete Algorithms*, Orlando, Florida,*
*1992, pp. 203-210. [PDF]
Published as Directed *s-t* Numberings,
Rubber Bands, and Testing Digraph *k*-Vertex
Connectivity, in *Combinatorica*
14(4) pp. 435-451, 1994. [PDF]

22.
John H. Reif
and Steve R. Tate, Dynamic Parallel Tree Contraction, *5th Annual ACM Symposium on Parallel Algorithms and Architectures
(SPAA'94)*, Cape May, NJ, June 1994. pp.114-121. Revised version submitted
for journal publication. [PDF]

23.
Deganit Armon and John H. Reif, A Dynamic Separator Algorithm with
Applications to Computational Geometry and Nested Dissection, *3rd Annual Workshop on Algorithms and Data
Structures (WADS '93)*, Montreal, Quebec, Canada, August, 1993, pp. 107-118.
[PDF]

24.
John H. Reif
and Doreen Yen, Derivation of Parallel Graph Connectivity Algorithms via Stream
Contraction, Duke University Technical Report, 1989. [PDF]