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]