default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDDonald B. Johnson 0001
Person information
- affiliation: Dartmouth College, Department of Computer Science, Hanover, NH, USA
- affiliation: Pennsylvania State University, Computer Science Departmentm University Park, PA, USA
- affiliation (PhD): Cornell University, Ithaca, NY, USA
Other persons with the same name
- Donald B. Johnson — disambiguation page
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 1997
[j26]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): 227-242 (1997)- 1996
- [j25]Donald B. Johnson, Panagiotis Takis Metaxas:
Optimal Algorithms for the Single and Multiple Vertex Updating Problems of a Minimum Spanning Tree. Algorithmica 16(6): 633-648 (1996) - [j24]Matthew Cheyney, Peter A. Gloor, Donald B. Johnson, Fillia Makedon, James Matthews, Panagiotis Takis Metaxas:
Toward Multimedia Conference Proceedings. Commun. ACM 39(1): 50-59 (1996) - [j23]Chris Armen, Donald B. Johnson:
Deterministic Leader Election on the Asynchronous QRQW PRAM. Parallel Process. Lett. 6(2): 247-250 (1996) - 1995
- [j22]Donald B. Johnson, Panagiotis Takis Metaxas:
A Parallel Algorithm for Computing Minimum Spanning Trees. J. Algorithms 19(3): 383-401 (1995) - [j21]Donald B. Johnson, Larry Raab:
A Tight Upper Bound on the Benefits of Replica Control Protocols. J. Comput. Syst. Sci. 51(2): 168-176 (1995) - 1994
- [j20]Donald B. Johnson, Larry Raab:
Complexity of Network Reliability and Optimal Resource Placement Problems. SIAM J. Comput. 23(3): 510-519 (1994) - 1992
- [j19]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): 315-333 (1992) - 1991
- [j18]Donald B. Johnson, Larry Raab:
Effects of Replication on Data Availability. Int. J. Comput. Simul. 1(4) (1991) - 1990
- [j17]Greg N. Frederickson, Donald B. Johnson:
Erratum: Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 19(1): 205-206 (1990) - 1987
- [j16]Donald B. Johnson:
Parallel algorithms for minimum cuts and maximum flows in planar networks. J. ACM 34(4): 950-967 (1987) - 1986
- [j15]Donald B. Johnson:
A Simple Proof of a Time-Space Trade-Off for Sorting with Linear Comparisons. Theor. Comput. Sci. 43: 345-350 (1986) - 1985
- [j14]Refael Hassin, Donald B. Johnson:
An O(n log2 n) Algorithm for Maximum Flow in Undirected Planar Networks. SIAM J. Comput. 14(3): 612-624 (1985) - 1984
- [j13]Greg N. Frederickson, Donald B. Johnson:
Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 13(1): 14-30 (1984) - 1983
- [j12]Greg N. Frederickson, Donald B. Johnson:
Finding k-th Paths and p-Centers by Generating and Searching Good Data Structures. J. Algorithms 4(1): 61-80 (1983) - 1982
- [j11]Teofilo F. Gonzalez, Donald B. Johnson:
Sorting Numbers in Linear Expected Time and Optimal Extra Space. Inf. Process. Lett. 15(3): 119-124 (1982) - [j10]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): 197-208 (1982) - [j9]Donald B. Johnson:
A Priority Queue in Which Initialization and Queue Operations Take O(log log D) Time. Math. Syst. Theory 15(4): 295-309 (1982) - 1980
- [j8]Teofilo F. Gonzalez, Donald B. Johnson:
A New Algorithm for Preemptive Scheduling of Trees. J. ACM 27(2): 287-312 (1980) - 1979
- [j7]Donald B. Johnson, Webb Miller, Brian Minnihan, Celia Wrathall:
Reducibility Among Floating-Point Graphs. J. ACM 26(4): 739-760 (1979) - 1978
- [j6]Donald B. Johnson, Samuel D. Kashdan:
Lower Bounds for Selection in X+Y and Other Multisets. J. ACM 25(4): 556-570 (1978) - [j5]Donald B. Johnson, Tetsuo Mizoguchi:
Selecting the Kth element in X + Y and X_1 + X_2 + ... + X_m. SIAM J. Comput. 7(2): 147-153 (1978) - 1977
- [j4]Donald B. Johnson:
Efficient Algorithms for Shortest Paths in Sparse Networks. J. ACM 24(1): 1-13 (1977) - 1975
- [j3]Donald B. Johnson:
Priority Queues with Update and Finding Minimum Spanning Trees. Inf. Process. Lett. 4(3): 53-57 (1975) - [j2]Donald B. Johnson:
Finding All the Elementary Circuits of a Directed Graph. SIAM J. Comput. 4(1): 77-84 (1975) - 1973
- [j1]Donald B. Johnson:
A Note on Dijkstra's Shortest Path Algorithm. J. ACM 20(3): 385-388 (1973)
Conference and Workshop Papers
- 1996
- [c10]Michael Goldweber, Donald B. Johnson:
Minimizing Access Costs in Replicated Distributed Syste (Abstract). PODC 1996: 56 - 1992
- [c9]Donald B. Johnson, Panagiotis Takis Metaxas:
Optimal Algorithms for the Vertex Updating Problem of a Minimum Spanning Tree. IPPS 1992: 306-314 - [c8]Donald B. Johnson, Panagiotis Takis Metaxas:
A Parallel Algorithm for Computing Minimum Spanning Trees. SPAA 1992: 363-372 - 1991
- [c7]Donald B. Johnson, Panagiotis Takis Metaxas:
Connected Components in O(\lg^3/2 |V|) Parallel Time for the CREW PRAM. FOCS 1991: 688-697 - [c6]Donald B. Johnson, Larry Raab:
Finding Optimal Quorum Assignments for Distributed Databases. ICPP (3) 1991: 214-218 - [c5]Donald B. Johnson, Larry Raab:
A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols. PODS 1991: 75-81 - 1983
- [c4]Donald B. Johnson, Shankar M. Venkatesan:
Partition of Planar Flow Networks (Preliminary Version). FOCS 1983: 259-263 - 1982
- [c3]Donald B. Johnson, Shankar M. Venkatesan:
Parallel Algorithms for Minimum Cuts and Maximum Flows in Planar Networks (Preliminary Version). FOCS 1982: 244-254 - 1980
- [c2]Greg N. Frederickson, Donald B. Johnson:
Generating and Searching Sets Induced by Networks. ICALP 1980: 221-233 - [c1]Greg N. Frederickson, Donald B. Johnson:
Generalized Selection and Ranking (Preliminary Version). STOC 1980: 420-428
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-25 05:46 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
