1.
John H. Reif,
The Complexity of Extending a Graph Imbedding. Computer Science Department,
University of Rochester, TR-42, October 1978. [PDF]
2.
Filotti, G. 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 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 Spirakis, Strong k-connectivity in Digraphs
and Random Digraphs, Harvard University TR-25-81. [PDF]
6. John H. Reif and Paul 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.
H. 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.
G. 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.
P. 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.
V. 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 in Journal of Computer and System Sciences, 49:3, December, 1994, pp. 517-561. [PostScript] [PDF] or [PostScript]
14.
V. 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.
V. 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.
H. 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.
Y. Han, V.
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 S. 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.
J. 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.
S. Nikoletseas, John H. Reif, P.G. Spirakis,
and M. 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.
J. 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 S. 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. [PostScript] [PDF]
23.
D. 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 D. Yen, Derivation of Parallel Graph Connectivity Algorithms via Stream
Contraction, Duke University Technical Report, 1989. [PDF]