S. L. Hakimi

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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 publications[edit]

  • 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.
  • 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. 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, 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, 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, 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."