Donald B. Johnson

Available identifiers

zbMath Open johnson.donald-bWikidataQ5293994 ScholiaQ5293994MaRDI QIDQ1079375

List of research outcomes

Publication	Date of Publication	Type
Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM	1997-06-16	Paper
Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree	1996-12-01	Paper
A Parallel Algorithm for Computing Minimum Spanning Trees	1996-04-11	Paper
Complexity of Network Reliability and Optimal Resource Placement Problems	1994-08-14	Paper
A simple proof of a time-space trade-off for sorting with linear comparisons	1986-01-01	Paper
An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks	1985-01-01	Paper
Generalized Selection and Ranking: Sorted Matrices	1984-01-01	Paper
Finding kth paths and p-centers by generating and searching good data structures	1983-01-01	Paper
A priority queue in which initialization and queue operations takeO(loglogD) time	1982-01-01	Paper
The complexity of selection and ranking in X+Y and matrices with sorted columns	1982-01-01	Paper
Sorting numbers in linear expected time and optimal extra space	1982-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3901005	1980-01-01	Paper
A New Algorithm for Preemptive Scheduling of Trees	1980-01-01	Paper
Reducibility Among Floating-Point Graphs	1979-01-01	Paper
Lower Bounds for Selection in X + Y and Other Multisets	1978-01-01	Paper
Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $	1978-01-01	Paper
An efficient algorithm for allocating paged, drum-like storage	1978-01-01	Paper
Efficient Algorithms for Shortest Paths in Sparse Networks	1977-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q4138132	1977-01-01	Paper
On batch scheduling of jobs with stochastic service times and cost structures on a single server	1976-01-01	Paper
A characterization ofLL(1) grammars	1976-01-01	Paper
Finding All the Elementary Circuits of a Directed Graph	1975-01-01	Paper
Priority queues with update and finding minimum spanning trees	1975-01-01	Paper
A Note on Dijkstra's Shortest Path Algorithm	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