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]