Древесная ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 60: | Строка 60: | ||
Бушитт и Тодинка [8] показали, что древесная ширина может быть вычислена за полиномиальное время для графов, имеющих полиномиальное число минимальных сепараторов. На этой основе были разработаны алгоритмы с полиномиальным временем выполнения для нескольких классов графов – таких как перестановочные графы или слабо триангулированные графы. | |||
== Применение == | == Применение == | ||