Kurt Mehlhorn

Kurt Mehlhorn
Born	(1949-08-29)29 August 1949 Ingolstadt,West Germany
Alma mater	Cornell University
Known for	LEDA
Awards	Leibniz Prize Konrad Zuse Medal(1995) EATCS Award Paris Kanellakis Award(2010)
Scientific career
Fields	Computer science
Institutions	Universität des Saarlandes
Doctoral advisor	Robert Lee Constable

Kurt Mehlhorn(born 29 August 1949) is a Germantheoretical computer scientist.He has been a vice president of theMax Planck Societyand is director of theMax Planck Institute for Computer Science.

Education and career

Mehlhorn graduated in 1971 from theTechnical University of Munich,where he studied computer science and mathematics, and earned his Ph.D. in 1974 fromCornell Universityunder the supervision ofRobert Constable.Since 1975 he has been on the faculty ofSaarland UniversityinSaarbrücken,Germany, where he was chair of the computer science department from 1976 to 1978 and again from 1987 to 1989. Since 1990 has been the director of the Max Planck Institute for Computer Science, also in Saarbrücken. He has been on the editorial boards of ten journals, a trustee of theInternational Computer Science InstituteinBerkeley, California,and a member of the board of governors ofJacobs University Bremen.He also served on the Engineering and Computer Science jury for theInfosys Prizefrom 2009 to 2011.

Awards and honors

He won theGottfried Wilhelm Leibniz Prizein 1986, theGay-Lussac-Humboldt-Prizein 1989, the Karl Heinz Beckurts Award in 1994, theKonrad Zuse Medalin 1995, theEATCS Awardin 2010,and theParis Kanellakis Awardin 2010. He was named a member of theAcademia Europaeain 1995,Fellowof theAssociation for Computing Machineryin 1999, a member of the Berlin-Brandenburg Academy of Sciences in 2001, a member of theGerman Academy of Sciences Leopoldinain 2004, a foreign member of theNational Academy of Engineeringin 2014, and a foreign member of theNational Academy of Sciencesin 2014.He has received honorary doctorates from theOtto von Guericke University of Magdeburgin 2002 and theUniversity of Waterlooin 2006.He is the 2014 winner of the Erasmus Medal of theAcademia Europaea.

Research

Mehlhorn is the author of several books and over 250 scientific publications,which include fundamental contributions todata structures,computational geometry,computer algebra,parallel computing,VLSI design,computational complexity,combinatorial optimization,andgraph algorithms.

Mehlhorn has been an important figure in the development ofalgorithm engineeringand is one of the developers ofLEDA,theLibrary of Efficient Data types and Algorithms.

Mehlhorn has played an important role in the establishment of several research centres for computer science in Germany. He was the driving forcebehind the establishment of aMax Planck Institutefor Computer Science in Germany, theMax Planck Institute for Computer Science(MPII). Mehlhorn is managing director of the institute and heads the department of algorithms and complexity. He also initiatedthe research center for computer science atDagstuhland theEuropean Symposium on Algorithms.

Books

• Mehlhorn, Kurt (1977),Effiziente Algorithmen,Stuttgart: Teubner.Revised and translated asData Structures and Algorithms,Springer-Verlag, 1984.
• Mehlhorn, Kurt (1984),Data Structures and Algorithms II: Graph Algorithms and NP-completeness,Springer-Verlag.
• Mehlhorn, Kurt (1984),Data Structures and Algorithms III: Multidimensional Searching and Computational Geometry,Springer-Verlag.
• Loeckx, Jacques; Mehlhorn, Kurt; Wilhelm, Reinhard (1988),Foundations of Programming Languages,J. Wiley,ISBN978-0-471-92139-4.
• Mehlhorn, Kurt; Näher, Stefan (1999),LEDA: A Platform for Combinatorial and Geometric Computing,Cambridge University Press,ISBN978-0-521-56329-1.
• Mehlhorn, Kurt;Sanders, Peter(2008),Algorithms and Data Structures: The Basic Toolbox,Springer,ISBN978-3-540-77977-3.

Selected publications

• Mehlhorn, Kurt; Schmidt, Erik M. (1982),"Las Vegas is better than determinism in VLSI and distributed computing"(PDF),Proc. 14th ACM Symp. Theory of Computing (STOC),pp. 330–337,doi:10.1145/800070.802208,ISBN978-0897910705,S2CID17932779.
• Mehlhorn, Kurt;Vishkin, Uzi(November 1984),"Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories"(PDF),Acta Informatica,21(4): 339–374,doi:10.1007/BF00264615,S2CID29789494.
• Alt, Helmut;Mehlhorn, Kurt; Wagener, Hubert;Welzl, Emo(1988),"Congruence, similarity, and symmetries of geometric objects"(PDF),Discrete and Computational Geometry,3(1): 237–256,doi:10.1007/BF02187910,S2CID5855400.
• Ahuja, Ravindra K.; Mehlhorn, Kurt;Orlin, James B.;Tarjan, Robert E.(April 1990),"Faster algorithms for the shortest path problem"(PDF),Journal of the Association for Computing Machinery,37(2): 213–223,CiteSeerX10.1.1.85.5847,doi:10.1145/77600.77615,hdl:1721.1/47994,S2CID5499589.
• Dietzfelbinger, Martin;Karlin, Anna;Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans;Tarjan, Robert E.(1994),"Dynamic perfect hashing: upper and lower bounds",SIAM Journal on Computing,23(4): 738–761,CiteSeerX10.1.1.30.8165,doi:10.1137/S0097539791194094.Also available asPrinceton TR-310-91.