唐纳德·布鲁斯·约翰逊

唐纳德·布鲁斯·约翰逊(英语:Donald Bruce Johnson,1933年12月16日—1994年11月10日[1][2][3]),美国计算机科学家,算法研究员,达特茅斯学院的计算机科学系主任[4]

个人经历

编辑

1973年,约翰逊在康奈尔大学取得了他的博士学位[5]。之后他又先后担任宾夕法尼亚州立大学计算机科学系教授和达特茅斯学院数学系教授职位[5]。1994年,达特茅斯学院计算机科学系成立[6] ,约翰逊任系主任[4]

学术贡献

编辑

约翰逊发明了数据结构d叉堆英语D-ary heap[7][8],此外提出了计算最短路约翰逊算法英语Johnson's algorithm[9][10]

参考文献

编辑
  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., Deterministic leader election on the asynchronous QRQW PRAM, Parallel Processing Letters, 1996, 6 (2): 247–250, doi:10.1142/S0129626496000248 .
  3. ^ Johnson's home page at Dartmouth as of 1997. [2017-04-23]. (原始内容存档于1997-06-05). , retrieved 2011-01-04.
  4. ^ 4.0 4.1 Gloor, P. A., Acknowledgements, Elements of hypermedia design: techniques for navigation & visualization in cyberspace, Birkhäuser: xvii, 1997 .
  5. ^ 5.0 5.1 Donald Bruce Johnson数学谱系计划的资料。.
  6. ^ History of Computer Science at Dartmouth College页面存档备份,存于互联网档案馆), retrieved 2011-01-04.
  7. ^ Johnson, D. B., Priority queues with update and finding minimum spanning trees, Information Processing Letters, 1975, 4: 53–57, doi:10.1016/0020-0190(75)90001-0 .
  8. ^ Tarjan, R. E., 3.2. d-heaps, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics 44, Society for Industrial and Applied Mathematics: 34–38, 1983 .
  9. ^ Johnson, Donald B., Efficient algorithms for shortest paths in sparse networks, ACM期刊, 1977, 24 (1): 1–13, doi:10.1145/321992.321993 .
  10. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, 算法导论, MIT Press and McGraw-Hill, 2001, ISBN 978-0-262-03293-3 . Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.