S. L. Hakimi

Seifollah Louis Hakimi is 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.^[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.^[2]

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

Selected publications

• 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: 135–147, 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: 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, 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.

References

1. 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.
2. S. L. Hakimi at the Mathematics Genealogy Project
3. 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.
4. 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.
5. Marianov, Vladimir; Serra, Daniel (2011), "Median problems in networks", in Eiselt, Horst A.; Marianov, Vladimir, Foundations of Location Analysis, International series in operations research & management science 155, Springer, doi:10.1007/978-1-4419-7572-0_3, 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."