Donald B. Johnson

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Connected components in $O(\log^{3/2}n)$ parallel time for the CREW PRAM Journal of Computer and System Sciences	1997-06-16	Paper
Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree Algorithmica	1996-12-01	Paper
A Parallel Algorithm for Computing Minimum Spanning Trees Journal of Algorithms	1996-04-11	Paper
Complexity of Network Reliability and Optimal Resource Placement Problems SIAM Journal on Computing	1994-08-14	Paper
A simple proof of a time-space trade-off for sorting with linear comparisons Theoretical Computer Science	1986-01-01	Paper
An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks SIAM Journal on Computing	1985-01-01	Paper
Generalized Selection and Ranking: Sorted Matrices SIAM Journal on Computing	1984-01-01	Paper
Finding kth paths and p-centers by generating and searching good data structures Journal of Algorithms	1983-01-01	Paper
A priority queue in which initialization and queue operations takeO(loglogD) time Mathematical Systems Theory	1982-01-01	Paper
The complexity of selection and ranking in X+Y and matrices with sorted columns Journal of Computer and System Sciences	1982-01-01	Paper
Sorting numbers in linear expected time and optimal extra space Information Processing Letters	1982-01-01	Paper
scientific article; zbMATH DE number 3709597 (Why is no real title available?)	1980-01-01	Paper
A New Algorithm for Preemptive Scheduling of Trees Journal of the ACM	1980-01-01	Paper
Reducibility Among Floating-Point Graphs Journal of the ACM	1979-01-01	Paper
Lower Bounds for Selection in X + Y and Other Multisets Journal of the ACM	1978-01-01	Paper
Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $ SIAM Journal on Computing	1978-01-01	Paper
An efficient algorithm for allocating paged, drum-like storage BIT Numerical Mathematics	1978-01-01	Paper
Efficient Algorithms for Shortest Paths in Sparse Networks Journal of the ACM	1977-01-01	Paper
scientific article; zbMATH DE number 3566166 (Why is no real title available?)	1977-01-01	Paper
On batch scheduling of jobs with stochastic service times and cost structures on a single server Journal of Computer and System Sciences	1976-01-01	Paper
A characterization ofLL(1) grammars BIT	1976-01-01	Paper
Finding All the Elementary Circuits of a Directed Graph SIAM Journal on Computing	1975-01-01	Paper
Priority queues with update and finding minimum spanning trees Information Processing Letters	1975-01-01	Paper
A Note on Dijkstra's Shortest Path Algorithm Journal of the ACM	1973-01-01	Paper
Density Bounds for the Sum of Divisors Function	1972-01-01	Paper

Research outcomes over time

This page was built for person: Donald B. Johnson

Publication	Date of Publication	Type
Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM Journal of Computer and System Sciences	1997-06-16	Paper
Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree Algorithmica	1996-12-01	Paper
A Parallel Algorithm for Computing Minimum Spanning Trees Journal of Algorithms	1996-04-11	Paper
Complexity of Network Reliability and Optimal Resource Placement Problems SIAM Journal on Computing	1994-08-14	Paper
A simple proof of a time-space trade-off for sorting with linear comparisons Theoretical Computer Science	1986-01-01	Paper
An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks SIAM Journal on Computing	1985-01-01	Paper
Generalized Selection and Ranking: Sorted Matrices SIAM Journal on Computing	1984-01-01	Paper
Finding kth paths and p-centers by generating and searching good data structures Journal of Algorithms	1983-01-01	Paper
A priority queue in which initialization and queue operations takeO(loglogD) time Mathematical Systems Theory	1982-01-01	Paper
The complexity of selection and ranking in X+Y and matrices with sorted columns Journal of Computer and System Sciences	1982-01-01	Paper
Sorting numbers in linear expected time and optimal extra space Information Processing Letters	1982-01-01	Paper
scientific article; zbMATH DE number 3709597 (Why is no real title available?)	1980-01-01	Paper
A New Algorithm for Preemptive Scheduling of Trees Journal of the ACM	1980-01-01	Paper
Reducibility Among Floating-Point Graphs Journal of the ACM	1979-01-01	Paper
Lower Bounds for Selection in X + Y and Other Multisets Journal of the ACM	1978-01-01	Paper
Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $ SIAM Journal on Computing	1978-01-01	Paper
An efficient algorithm for allocating paged, drum-like storage BIT Numerical Mathematics	1978-01-01	Paper
Efficient Algorithms for Shortest Paths in Sparse Networks Journal of the ACM	1977-01-01	Paper
scientific article; zbMATH DE number 3566166 (Why is no real title available?)	1977-01-01	Paper
On batch scheduling of jobs with stochastic service times and cost structures on a single server Journal of Computer and System Sciences	1976-01-01	Paper
A characterization ofLL(1) grammars BIT	1976-01-01	Paper
Finding All the Elementary Circuits of a Directed Graph SIAM Journal on Computing	1975-01-01	Paper
Priority queues with update and finding minimum spanning trees Information Processing Letters	1975-01-01	Paper
A Note on Dijkstra's Shortest Path Algorithm Journal of the ACM	1973-01-01	Paper
Density Bounds for the Sum of Divisors Function	1972-01-01	Paper