Длинные пути и циклы за пределами экстремальной теории графовLong paths and cycles beyond extremal graph theory

Диссертация посвящена исследованию вычислительной сложности задачпоиска длинных путей и циклов в двусвязных графах. В работеобъединяются классические результаты теории графов и современныеалгоритмические методы для эффективного поиска путей и циклов в графахс большой минимальной или средней степенью. Предложены новые структурные декомпозиции, обобщающие теоремы Дирака иЭрдёша–Галлаи. На их основе разработан общий подход к расширениюприменимости приближённых алгоритмов поиска путей и циклов, а такжеполучены новые точные параметризованные алгоритмы, отвечающие на рядоткрытых вопросов в данной области. Полученные результаты развивают методы графовых алгоритмов идемонстрируют перспективность объединения идей экстремальной теорииграфов с подходами теории вычислительной сложности.