• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Задача о реберном списковом ранжировании является обобщением классической задачи о раскраске ребер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность данной задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определенные и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся совокупность "критических" классов графов, включение которых в конечно определенный класс эквивалентно "труднорешаемости" задачи о реберном списковом ранжировании в этом классе. По-видимому, это вообще первый результат о полном таком описании для неискусственных NP-полных задач на графах. Конструктивно доказывается, что для этой задачи среди минимальных по включению наследственных случаев "труднорешаемости" имеется всего 5 конечно определенных классов и 1 минорно замкнутый класс