S. L. Hakimi

Seifollah Louis Hakimi (1932–June 23, 2005) 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. He was chair of the Department of Electrical Engineering at University of California, Davis, from 1986 to 1996.

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.

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

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 (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 10.1.1.63.3708, 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.