1.
J.H. Reif, The
Complexity of Extending a Graph Imbedding. Computer Science Department,
University of Rochester, TR-42, October 1978. [PDF]
2.
G. Miller, I.
Filotti, and J.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.
J.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, pages 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.
J.H. Reif and P.
Spirakis, K-connectivity in Random Undirected Graphs, Discrete Mathematics, Vol.
54, No. 2, April 1985, pp. 181-191. [PDF]
5.
J.H. Reif and P.
Spirakis, Strong k-connectivity in Digraphs and Random Digraphs, Harvard
University TR-25-81. [PDF]
6. J.H. Reif and P. Spirakis, Expected Parallel Time
and Sequential Space Complexity of Graph and Digraph Problems, Published in Algorithmica, Special Issue on Graph Algorithms, Vol. 7,
Numbers 5 & 7, pp. 597-630, 1992. [PDF]
7. J.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. J.H. Reif, Depth-First Search is Inherently Sequential.
Information Processing Letters,
Vol. 20, No. 5, June 12, 1985, pp.
229-234. [PDF]
9.
J.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 J.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 J.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, 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 J.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
J.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 J.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.
Pan and J.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, 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 J.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
J.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.
J.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 J.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 J.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, J.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'93), Szeged, Hungary, July 1993. [PDF]
21.
J. Cheriyan and J.H.
Reif, Algebraic Methods for Testing the k-Vertex Connectivity of Directed Graphs, 3rd Annual ACM-SIAM
Symposium on Discrete Algorithms,
Orlando, Florida, 1992. [PDF]
Published as Directed s-t
Numberings, Rubber Bands, and Testing Digraph k-Vertex Connectivity, in Combinatorica 14(4) 435-451, 1994. [PDF]
22.
J.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 J.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, p.107-118. [PDF]
24.
J.H. Reif and D. Yen,
Derivation of Parallel Graph Connectivity Algorithms via Stream Contraction,
Duke University Technical Report, 1989. [PDF]