Donald B. Johnson

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
  1. date from Author's thesis biographyJohnson, Donald B., Algorithms for shortest paths
  2. 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.
  3. "Johnson's home page at Dartmouth as of 1997". Archived from the original on June 5, 1997. Retrieved 2017-04-23.CS1 maint: BOT: original-url status unknown (link), retrieved 2011-01-04.
  4. Gloor, P. A. (1997), "Acknowledgements", Elements of hypermedia design: techniques for navigation & visualization in cyberspace, Birkhäuser, p. xvii.
  5. Donald Bruce Johnson at the Mathematics Genealogy Project.
  6. History of Computer Science at Dartmouth College Archived October 31, 2010, at the Wayback Machine, retrieved 2011-01-04.
  7. Johnson, D. B. (1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4: 53–57, doi:10.1016/0020-0190(75)90001-0.
  8. Tarjan, R. E. (1983), "3.2. d-heaps", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, 44, Society for Industrial and Applied Mathematics, pp. 34–38.
  9. 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.
  10. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.