Donald B. Johnson

Publication Activity (10 Years)

Years Active: 1973-1997
Publications (10 Years): 0

Publications

Donald B. Johnson, Panagiotis Takis Metaxas
Connected Components in O (log^3/2 n) Parallel Time for the CREW PRAM. J. Comput. Syst. Sci. 54 (2) (1997)
Michael Goldweber, Donald B. Johnson
Minimizing Access Costs in Replicated Distributed Syste (Abstract). PODC (1996)
Matthew Cheyney, Peter A. Gloor, Donald B. Johnson, Fillia Makedon, James Matthews, Panagiotis Takis Metaxas
Toward Multimedia Conference Proceedings. Commun. ACM 39 (1) (1996)
Donald B. Johnson, Panagiotis Takis Metaxas
Optimal Algorithms for the Single and Multiple Vertex Updating Problems of a Minimum Spanning Tree. Algorithmica 16 (6) (1996)
Chris Armen, Donald B. Johnson
Deterministic Leader Election on the Asynchronous QRQW PRAM. Parallel Process. Lett. 6 (2) (1996)
Donald B. Johnson, Larry Raab
A Tight Upper Bound on the Benefits of Replica Control Protocols. J. Comput. Syst. Sci. 51 (2) (1995)
Donald B. Johnson, Panagiotis Takis Metaxas
A Parallel Algorithm for Computing Minimum Spanning Trees. J. Algorithms 19 (3) (1995)
Donald B. Johnson, Larry Raab
Complexity of Network Reliability and Optimal Resource Placement Problems. SIAM J. Comput. 23 (3) (1994)
Donald B. Johnson, Panagiotis Takis Metaxas
Optimal Algorithms for the Vertex Updating Problem of a Minimum Spanning Tree. IPPS (1992)
Donald B. Johnson, Panagiotis Takis Metaxas
A Parallel Algorithm for Computing Minimum Spanning Trees. SPAA (1992)
Peter A. Gloor, Donald B. Johnson, Fillia Makedon, Panagiotis Takis Metaxas
A Visualization System for Correctness Proofs of Graph Algorithms. Comput. Sci. Educ. 3 (3) (1992)
Donald B. Johnson, Larry Raab
A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols. PODS (1991)
Donald B. Johnson, Larry Raab
Finding Optimal Quorum Assignments for Distributed Databases. ICPP (3) (1991)
Donald B. Johnson, Larry Raab
Effects of Replication on Data Availability. Int. J. Comput. Simul. 1 (4) (1991)
Donald B. Johnson, Panagiotis Takis Metaxas
Connected Components in O(\lg^3/2 |V|) Parallel Time for the CREW PRAM FOCS (1991)
Greg N. Frederickson, Donald B. Johnson
Erratum: Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 19 (1) (1990)
Donald B. Johnson
Parallel algorithms for minimum cuts and maximum flows in planar networks. J. ACM 34 (4) (1987)
Donald B. Johnson
A Simple Proof of a Time-Space Trade-Off for Sorting with Linear Comparisons. Theor. Comput. Sci. 43 (1986)
Refael Hassin, Donald B. Johnson
n) Algorithm for Maximum Flow in Undirected Planar Networks. SIAM J. Comput. 14 (3) (1985)
Greg N. Frederickson, Donald B. Johnson
Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 13 (1) (1984)
Greg N. Frederickson, Donald B. Johnson
Finding k-th Paths and p-Centers by Generating and Searching Good Data Structures. J. Algorithms 4 (1) (1983)
Donald B. Johnson, Shankar M. Venkatesan
Partition of Planar Flow Networks (Preliminary Version) FOCS (1983)
Greg N. Frederickson, Donald B. Johnson
The Complexity of Selection and Ranking in X+Y and Matrices with Sorted Columns. J. Comput. Syst. Sci. 24 (2) (1982)
Donald B. Johnson
A Priority Queue in Which Initialization and Queue Operations Take O(log log D) Time. Math. Syst. Theory 15 (4) (1982)
Donald B. Johnson, Shankar M. Venkatesan
Parallel Algorithms for Minimum Cuts and Maximum Flows in Planar Networks (Preliminary Version) FOCS (1982)
Teofilo F. Gonzalez, Donald B. Johnson
Sorting Numbers in Linear Expected Time and Optimal Extra Space. Inf. Process. Lett. 15 (3) (1982)
Teofilo F. Gonzalez, Donald B. Johnson
A New Algorithm for Preemptive Scheduling of Trees. J. ACM 27 (2) (1980)
Greg N. Frederickson, Donald B. Johnson
Generalized Selection and Ranking (Preliminary Version) STOC (1980)
Greg N. Frederickson, Donald B. Johnson
Generating and Searching Sets Induced by Networks. ICALP (1980)
Donald B. Johnson, Webb Miller, Brian Minnihan, Celia Wrathall
Reducibility Among Floating-Point Graphs. J. ACM 26 (4) (1979)
Donald B. Johnson, Samuel D. Kashdan
Lower Bounds for Selection in X+Y and Other Multisets. J. ACM 25 (4) (1978)
Donald B. Johnson, Tetsuo Mizoguchi
Selecting the Kth element in X + Y and X_1 + X_2 + ... + X_m. SIAM J. Comput. 7 (2) (1978)
Donald B. Johnson
Efficient Algorithms for Shortest Paths in Sparse Networks. J. ACM 24 (1) (1977)
Donald B. Johnson
Finding All the Elementary Circuits of a Directed Graph. SIAM J. Comput. 4 (1) (1975)
Donald B. Johnson
Priority Queues with Update and Finding Minimum Spanning Trees. Inf. Process. Lett. 4 (3) (1975)
Donald B. Johnson
A Note on Dijkstra's Shortest Path Algorithm. J. ACM 20 (3) (1973)