Аноним

Путевая ширина графа: различия между версиями

Материал из WEGA

Путевая ширина графа (посмотреть исходный код)

Версия от 01:03, 13 августа 2012

68 байт добавлено ,  13 августа 2012
→‎Открытые вопросы
Строка 72: Строка 72:




3. Найти Bk для значений k больше 3. Единственный структурный результат Bk заключается в том, что его планарные элементы являются либо самодвойственными, либо попарно двойственными. Это заключение следует из того факта, что двойственные планарные графы имеют одинаковую путевую ширину [29, 16].
3. Найти <math>\mathfrak{B}_k</math> для значений k больше 3. Единственный структурный результат <math>\mathfrak{B}_k</math> заключается в том, что его планарные элементы являются либо самодвойственными, либо попарно двойственными. Это заключение следует из того факта, что двойственные планарные графы имеют одинаковую путевую ширину [29, 16].




4. Найти точный алгоритм для вычисления путевой ширины сложности O*(2") (нотация O*() предполагает, что неэкспоненциальные члены классической нотации O() отбрасываются).
4. Найти точный алгоритм для вычисления путевой ширины сложности <math>O*(2^n) \, </math> (нотация O*() предполагает, что неэкспоненциальные члены классической нотации O() отбрасываются).




Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10324