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

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

21 байт добавлено , 13 августа 2012

4446

правок

Версия от 01:03, 13 августа 2012 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Открытые вопросы) ← Предыдущая правка		Версия от 01:04, 13 августа 2012 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Открытые вопросы) Следующая правка →
Строка 78:		Строка 78:


	5. Зависимость линейного по времени алгоритма вычисления путевой ширины от k очень велика [3]. Найти алгоритм, состоящий из 2O(k) ~~• nO~~(1) шагов, который определяет верность утверждения о том, что путевая ширина входного графа с n вершинами составляет не более k.		5. Зависимость линейного по времени алгоритма вычисления путевой ширины от k очень велика [3]. Найти алгоритм, состоящий из <math>2^{O(k)} \cdot n^{O(1)}</math> шагов, который определяет верность утверждения о том, что путевая ширина входного графа с n вершинами составляет не более k.

	== См. также ==		== См. также ==