4551
правка
Двумерность: различия между версиями
Материал из WEGA
м
→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
Можно ли обобщить алгоритмические результаты (теоремы 3 и 4) для решения задач о двумерности со сжатием, не ограничивающихся графами, свободными от апексных миноров? Известно, что лежащая в основе этих результатов теорема 1 не допускает обобщения [1]. Тем не менее, теорему 3 удалось обобщить для одной конкретной задачи о двумерности со сжатием – доминирующего множества [ ]. | Можно ли обобщить алгоритмические результаты (теоремы 3 и 4) для решения задач о двумерности со сжатием, не ограничивающихся графами, свободными от апексных миноров? Известно, что лежащая в основе этих результатов теорема 1 не допускает обобщения [1]. Тем не менее, теорему 3 удалось обобщить для одной конкретной задачи о двумерности со сжатием – доминирующего множества [3]. | ||
Можно ли обобщить схемы аппроксимации с полиномиальным временем выполнения из теоремы 4 до алгоритмических задач более общего вида, не сопоставленных напрямую с двумерными параметрами? Один пример семейства подобных задач общего вида появляется при назначении вершинам и/или ребрам весов и необходимости вычислить, например, доминирующее множество с минимальным весом. Еще один пример такой задачи возникает при накладывании ограничений (например, на покрытие или доминирование) только на подмножества вершин и/или ребер. В качестве примеров таких задач можно привести алгоритмы построение дерева Штейнера и разрывающего множества вершин. | Можно ли обобщить схемы аппроксимации с полиномиальным временем выполнения из теоремы 4 до алгоритмических задач более общего вида, не сопоставленных напрямую с двумерными параметрами? Один пример семейства подобных задач общего вида появляется при назначении вершинам и/или ребрам весов и необходимости вычислить, например, доминирующее множество с минимальным весом. Еще один пример такой задачи возникает при накладывании ограничений (например, на покрытие или доминирование) только на подмножества вершин и/или ребер. В качестве примеров таких задач можно привести алгоритмы построение дерева Штейнера и разрывающего множества вершин. | ||
