Donald B. Johnson
Donald B. Johnson | |
|---|---|
| Born | Donald Bruce Johnson (1933年12月16日)December 16, 1933 |
| Died | September 10, 1994(1994年09月10日) (aged 60) |
| Nationality | American |
| Education | Cornell University |
| Occupation | computer scientist |
| Employer(s) | Dartmouth College Pennsylvania State University |
| Known for | founding chair, Dartmouth College computer science department |
| Notable work | d-ary heap data structure Johnson's algorithm |
Donald Bruce Johnson (December 16, 1933 – September 10, 1994)[1] [2] [3] was an American computer scientist, a researcher in the design and analysis of algorithms, and the founding chair of the computer science department at Dartmouth College.[4]
Johnson received his Ph.D. from Cornell University in 1973 under the supervision of David Gries.[5] He took a faculty position in the computer science department at Pennsylvania State University, and later moved to the department of mathematics at Dartmouth.[5] When the Dartmouth computer science department was founded in 1994,[6] he became its first chair.[4]
Johnson invented the d-ary heap data structure,[7] [8] and is also known for Johnson's algorithm for the all-pairs shortest path problem.[9] [10]
References
[edit ]- ^ date from Author's thesis biographyJohnson, Donald B., Algorithms for shortest paths
- ^ Death date from author listing of Armen, Chris; Johnson, Donald B. (1996), "Deterministic leader election on the asynchronous QRQW PRAM", Parallel Processing Letters, 6 (2): 247–250, doi:10.1142/S0129626496000248 .
- ^ "Johnson's home page at Dartmouth as of 1997". Archived from the original on June 5, 1997. Retrieved April 23, 2017.
{{cite web}}: CS1 maint: bot: original URL status unknown (link), retrieved 2011年01月04日. - ^ a b Gloor, P. A. (1997), "Acknowledgements", Elements of hypermedia design: techniques for navigation & visualization in cyberspace, Birkhäuser, p. xvii.
- ^ a b Donald Bruce Johnson at the Mathematics Genealogy Project.
- ^ History of Computer Science at Dartmouth College Archived October 31, 2010, at the Wayback Machine, retrieved 2011年01月04日.
- ^ Johnson, D. B. (1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4 (3): 53–57, doi:10.1016/0020-0190(75)90001-0 .
- ^ Tarjan, R. E. (1983), "3.2. d-heaps", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, pp. 34–38.
- ^ Johnson, Donald B. (1977), "Efficient algorithms for shortest paths in sparse networks", Journal of the ACM , 24 (1): 1–13, doi:10.1145/321992.321993 , S2CID 207678246 .
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms , MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3 . Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.