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]