Donald B. Johnson

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