Najiba Sbihi - Wikipedia

From Wikipedia, the free encyclopedia

Najiba Sbihi (born 1953)^[1] is a Moroccan mathematician and operations researcher, known for her contributions to graph theory and graph algorithms.

Sbihi earned a degree from the Faculty of Sciences of Mohammed V University in Rabat, Morocco in 1973. She continued her studies in France at Joseph Fourier University in Grenoble, first in computer science in which she earned a bachelor's degree in 1975. Continuing in operations research, she earned a diplôme d'études approfondies in 1976,^[2] a doctorat de troisième cycle in 1978 under the supervision of Michel Sakarovitch,^[1] and a doctorat d'état in 1987, supervised by Jean Fonlupt.^[3] Her doctoral study also included research in Canada with Jack Edmonds at the University of Waterloo and with Václav Chvátal at McGill University.^[2]

She worked with the Moroccan National Center for Scientific and Technical Research until, in 1992, becoming a professor of industrial engineering in the Mohammadia School of Engineering in Rabat. She headed the Department of Industrial Engineering from 1995 to 1997.^[2]

Sbihi's contributions to graph theory and graph algorithms include the discovery that the maximum independent set problem can be solved in polynomial time on claw-free graphs.^[A] With Chvátal, she proved a special case of the strong perfect graph theorem, for the graphs that have no bull graph as an induced subgraph.^[B] Their work in this area introduced a type of graph decomposition that was central to the eventual proof of the full strong perfect graph theorem.^[4] She and Chvátal also devised efficient algorithms for recognizing the claw-free perfect graphs,^[C] and later she and Bruce Reed showed how to recognize the Bull-free perfect graphs.^[D]