Najiba Sbihi

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

Education and career

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]

Contributions

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]

Selected publications

A.

Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile", Discrete Mathematics, 29 (1): 53–76, doi:10.1016/0012-365X(90)90287-R, MR 0553650

B.

Chvátal, Vašek; Sbihi, Najiba (1987), "Bull-free Berge graphs are perfect", Graphs and Combinatorics, 3 (2): 127–139, doi:10.1007/BF01788536, MR 0932129

C.

Chvátal, V.; Sbihi, N. (1988), "Recognizing claw-free perfect graphs", Journal of Combinatorial Theory, Series B, 44 (2): 154–176, doi:10.1016/0095-8956(88)90085-8, MR 0930204

D.

Reed, Bruce; Sbihi, Najiba (1995), "Recognizing bull-free perfect graphs", Graphs and Combinatorics, 11 (2): 171–178, doi:10.1007/BF01929485, MR 1341480

References

^ ^a ^b Étude des stables dans les graphes sans étoile, Joseph Fourier University, 1978, retrieved 2024-10-16
^ ^a ^b ^c Or_Afri_Icons 6: Pr. Najiba Sbihi, OR@AFRICA, 2024, retrieved 2024-10-16 – via Linkedin
^ Sbihi, Najiba; Fonlupt, Jean (January 1987), "Contribution à l'étude des stables dans un graphe par une approche algorithmique", Theses.fr, retrieved 2024-10-16
^ Avis, David; Bondy, Adrian; Cook, William; Reed, Bruce (June 2007), "Vašek Chvátal: A Very Short Introduction" (PDF), Graphs and Combinatorics, 23 (S1): 41–65, doi:10.1007/s00373-007-0721-4

[d3c-1] Étude des stables dans les graphes sans étoile, Joseph Fourier University, 1978, retrieved 2024-10-16

[ora-2] Or_Afri_Icons 6: Pr. Najiba Sbihi, OR@AFRICA, 2024, retrieved 2024-10-16 – via Linkedin

[theses-3] Sbihi, Najiba; Fonlupt, Jean (January 1987), "Contribution à l'étude des stables dans un graphe par une approche algorithmique", Theses.fr, retrieved 2024-10-16

[abc-4] Avis, David; Bondy, Adrian; Cook, William; Reed, Bruce (June 2007), "Vašek Chvátal: A Very Short Introduction" (PDF), Graphs and Combinatorics, 23 (S1): 41–65, doi:10.1007/s00373-007-0721-4

[1]

[2]

[3]

[4]