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 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.