S. L. Hakimi

Seifollah Louis Hakimi (1932 – June 23, 2005)[1] was an Iranian-American mathematician born in Iran, a professor emeritus at Northwestern University, where he chaired the department of electrical engineering from 1973 to 1978.[2] He was Chair of the Department of Electrical Engineering at University of California, Davis, from 1986 to 1996.[1]

Hakimi received his Ph.D. from the University of Illinois at Urbana-Champaign in 1959, under the supervision of Mac Van Valkenburg. He has over 100 academic descendants, most of them via his student Narsingh Deo.[3]

He is known for characterizing the degree sequences of undirected graphs,[4] for formulating the Steiner tree problem on networks,[5] and for his work on facility location problems on networks.[6]

Selected publicationsEdit

  • Hakimi, S. L. (1963), "On realizability of a set of integers as degrees of the vertices of a linear graph. II. Uniqueness", J. Soc. Indust. Appl. Math., 11 (1): 135–147, doi:10.1137/0111010, JSTOR 2098770, MR 0153001.
  • Hakimi, S. L. (1964), "Optimum locations of switching centers and the absolute centers and medians of a graph", Operations Research, 12 (3): 450–459, doi:10.1287/opre.12.3.450.
  • Hakimi, S. L. (1971), "Steiner's problem in graphs and its implications", Networks, 1 (2): 113–133, doi:10.1002/net.3230010203, MR 0295947.
  • Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H. (1988), "The complexity of searching a graph", Journal of the ACM, 35 (1): 18–44, CiteSeerX, doi:10.1145/42267.42268, S2CID 1521081.
  • Bauer, D.; Hakimi, S. L.; Schmeichel, E. (1990), "Recognizing tough graphs is NP-hard", Discrete Applied Mathematics, 28 (3): 191–195, doi:10.1016/0166-218X(90)90001-S, MR 1074858.


  1. ^ a b Pat Bailey (July 21, 2006). "Harold Olmo: Pioneering wine, grape scientist, and other obituaries". UCDavis. Archived from the original on 29 August 2017. Retrieved 29 August 2017.
  2. ^ Fine, Morris E. (ed.), Tech, the early years: An anthology of the history of the technological institute at Northwestern University from 1939 to 1969 (PDF), p. 103, archived from the original (PDF) on 2013-12-03.
  3. ^ S. L. Hakimi at the Mathematics Genealogy Project
  4. ^ Allenby, R.B.J.T.; Slomson, Alan (2011), "Theorem 9.3: the Havel–Hakimi theorem", How to Count: An Introduction to Combinatorics, Discrete Mathematics and Its Applications (2nd ed.), CRC Press, p. 159, ISBN 9781420082616, archived from the original on 2014-01-01, retrieved 2016-04-28, A proof of this theorem was first published by Václav Havel ... in 1963 another proof was published independently by S. L. Hakimi.
  5. ^ Hwang, F. K.; Richards, D. S.; Winter, P. (1992), The Steiner Tree Problem, Annals of Discrete Mathematics, Elsevier, p. 94, ISBN 9780080867939, archived from the original on 2014-01-01, retrieved 2016-04-28, The Steiner tree problem in networks was originally formulated by Hakimi and independently by Levin in 1971.
  6. ^ Marianov, Vladimir; Serra, Daniel (2011), "Median problems in networks", in Eiselt, Horst A.; Marianov, Vladimir (eds.), Foundations of Location Analysis, International series in operations research & management science, 155, Springer, pp. 39–59, doi:10.1007/978-1-4419-7572-0_3, hdl:10230/4796, ISBN 9781441975720. On p. 53 Archived 2014-01-01 at the Wayback Machine, Marianov and Serra write "The impact of Hakimi's two contributions is hard to overstate. A common opinion among location researchers is that the paper by Hakimi (1964) strongly contributed to trigger the interest in location theory and analysis, and started a long string of related publications that does not seem to be decreasing."