Papers by Reif on Sequential and Parallel Graph Algorithms (24 papers)

 

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]