Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 20: | Строка 20: | ||
== Основные результаты == | == Основные результаты == | ||
'''Алгоритмы вычисления путевой ширины''' | '''Алгоритмы вычисления путевой ширины''' | ||
Вычисление путевой ширины представляет собой NP-полную задачу ([29]). Более того, задача является NP-полной, даже если мы ограничим ее входные графы классом расщепляемых графов или двудольных графов [20]. | Вычисление путевой ширины представляет собой NP-полную задачу ([29]). Более того, задача является NP-полной, даже если мы ограничим ее входные графы классом расщепляемых графов или двудольных графов [20]. | ||