Анализ сложности задачи о рёберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами

Описаны все наследственные классы графов, определяемые не более чем тремя запрещёнными порождёнными подграфами (обструкциями), для которых задача о рёберном списковом ранжировании полиномиально разрешима. В основе алгоритма распознавания сложностного статуса лежит установление принадлежности обструкций некоторым специальным (“критическим”) классам графов. Частью множества таких специальных классов являются минимальные по включению наследственные случаи NP-полноты рассматриваемой задачи. Все классы данного типа, определяемые тремя и менее обструкциями, описаны. Ил. 4, библиогр. 14.