Наджиба Сбихи (родилась в 1953 году) [1] — марокканский математик и исследователь операций , известная своим вкладом в теорию графов и графовые алгоритмы .
Сбихи получила степень на факультете наук Университета Мухаммеда V в Рабате , Марокко, в 1973 году. Она продолжила обучение во Франции в Университете Жозефа Фурье в Гренобле , сначала по специальности «компьютерные науки», где она получила степень бакалавра в 1975 году. Продолжая изучать исследования операций , она получила диплом о продвинутых исследованиях в 1976 году [2], докторскую степень третьего цикла в 1978 году под руководством Мишеля Сакаровича [1] и докторскую степень в 1987 году под руководством Жана Фонлупа [3] . Ее докторская диссертация также включала исследования в Канаде с Джеком Эдмондсом в Университете Ватерлоо и с Вацлавом Хваталом в Университете Макгилла [2] .
Она работала с Марокканским национальным центром научных и технических исследований, пока в 1992 году не стала профессором промышленной инженерии в Школе инженерии Мохаммадия в Рабате. Она возглавляла кафедру промышленной инженерии с 1995 по 1997 год. [2]
Вклад Сбихи в теорию графов и графовые алгоритмы включает открытие того, что задача максимального независимого множества может быть решена за полиномиальное время для графов без клешней . [A] Совместно с Хваталом она доказала частный случай теоремы о сильном совершенном графе для графов, не имеющих бычьего графа в качестве индуцированного подграфа . [B] Их работа в этой области представила тип декомпозиции графа, который был центральным для окончательного доказательства теоремы о полном сильном совершенном графе. [4] Она и Хватал также разработали эффективные алгоритмы для распознавания совершенных графов без клешней, [C] а позже она и Брюс Рид показали, как распознавать совершенные графы без быков. [D]