4430
правок
Остовное дерево с максимальным количеством листьев: различия между версиями
Материал из WEGA
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 18:53, 13 августа 2016
, 13 августа 2016нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 126: | Строка 126: | ||
Таблица 1. Экология сложности параметров | Таблица 1. Экология сложности параметров | ||
Здесь используются следующие сокращения: TW – это древесная ширина дерева (TREEWIDTH), BW – ширина полосы (BANDWIDTH), VC – вершинное покрытие (VERTEX COVER), DS – доминирующее множество (DOMINATING SET), G – род (GENUS), а ML – максимальное количество листьев (MAX LEAF). Обозначение во второй строке и четвертом столбце говорит о том, существует ли FPT-алгоритм для решения задачи DOMINATING SET на графе G с шириной полосы не более k. Обозначение в четвертой строке и втором столбце говорит о том, что неизвестно, может ли задача BANDWIDTH быть оптимально решена FPT-алгоритмом, если параметром является граница числа доминирования входного графа. | |||
MAX LEAF применяется к последней строке таблицы. Для графов с максимальным количеством листьев, ограниченным k, максимальный размер независимого множества может быть вычислен за время O*(2,972k) на основе редукции ядра размером не более 7k. Использование результата решения одной задачи в качестве исходных данных для другой задачи оказывается весьма практичным. | |||
== Применение == | |||
Задача построения остовного дерева с максимальным количеством листьев применяется в расчетах компьютерной графики с целью создания представлений полосы треугольников для быстрого интерактивного рендеринга [ ]. Также она находит применение в области перераспределения трафика и проектирования сетей – например, для проектирования оптических сетей и распределения используемых длин волн для снижения стоимости сети – в терминах оконечного оборудования либо электронных переключателей [ ]. Задача о минимальной энергии в беспроводных сетях заключается в нахождении радиус-вектора передачи для всех станций таким образом, чтобы полная мощность излучения всей сети была насколько возможно малой. Ограниченная версия этой задачи эквивалентна задаче нахождения остовного дерева с максимальным количеством листьев [ ]. Задача поиска остовных деревьев с большим числом листьев эквивалентна задаче поиска небольших связных доминирующих множеств и в связи с этим также носит название задачи о минимальном связном доминирующем множестве [13]. | |||
== Открытые вопросы == | |||
Стратегии ветвления | |||
Хотя экстремальные структуры в определенном смысле представляют собой правильный подход к разработке FPT-алгоритма, этот подход не единственный. В частности, он не дает ответа на вопрос, что делать с ядром. Остается открытым вопрос поиска общих стратегий использования «структурной теории с подходящими параметрами» в стратегиях ветвления при анализе ядер в сложных задачах. | |||
Кернелизуемость Тьюринга | |||
Преобразование с полиномиальным временем выполнения (x, k) к более простому редуцированному экземпляру (x0, k0) является преобразованием «от многих к одному». Можно обобщить понятие редукции «от многих к одному» до редукции Тьюринга. Как должен развиваться поиск экстремальных структур с полиномиальным временем выполнения в контексте такого менее жесткого FPT-алгоритма? | |||
Алгоритмические формы подхода на базе граничной леммы | |||
Из гипотезы граничной леммы о том, что (G, k) является «да-экземпляром», следует, что существует структура, являющаяся свидетелем для данного факта. Не делается предположений о том, что к этой структуре имеется алгоритмический доступ, а когда будут найдены правила редукции, они должны представлять собой преобразования, которые могут быть применены к (G, k) и структуре, которая может быть найдена в (G, k) за полиномиальное время. Иными словами, правила редукции не могут быть определены относительно структуры-свидетеля. Возможно ли описать более общие подходы к кернелизации, при которых структура-свидетель, используемая в ходе доказательства граничной леммы, может быть вычислена за полиномиальное время, и эта структура предоставит условный контекст для некоторых правил редукции? Как эти подходы изменят метод использования экстремальной структуры? | |||
Задача с аннотациями | |||
Можно рассмотреть обобщенную задачу построения остовного дерева с максимальным количеством листьев (MAX LEAF), в которой вершины и ребра имеют различные аннотации, говорящие о том, какие вершины должны быть листьями (и внутренними вершинами) в решении, и т.д. В общем случае подобная обобщенная форма задачи будет сложнее вышеописанной более простой формы. Однако некоторые из «наиболее известных» FPT-алгоритмов для решения различных задач основаны на таких обобщенных формах с аннотациями. В качестве примеров можно привести алгоритмы нахождения доминирующего множества для планарного графа (PLANAR DOMINATING SET) и разрывающего множества вершин (FEEDBACK VERTEX SET) [ ]. Должны ли аннотации быть непременным компонентом рецепта наилучшего возможного алгоритма кернелизации с полиномиальным временем выполнения? | |||
== См. также == | |||
* ''[[Связное доминирующее множество]] | |||
* ''[[Редукция данных для доминирования в графах]] | |||
== Литература == | |||
1. Bonsma, P.: Spanning trees with many leaves: new extremal results and an improved FPT algorithm. Memorandum Department of Applied Mathematics, vol. 1793, University of Twente,Enschede (2006) | |||
2. Bonsma, P., Brueggemann, T., Woeginger, G.: A faster FPT algorithm for finding spanning trees with many leaves. Proceedings of MFCS 2003. Lecture Notes in Computer Science, vol. 2747, pp. 259-268. Springer, Berlin (2003) | |||
3. Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999) | |||
4. Dehne, F., Fellows, M., Langston, M., Rosamond, F., Stevens, K.: An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. Proceedings COCOON 2005. Lecture Notes in Computer Science, vol. 3595, pp. 859-869. Springer, Berlin (2005) | |||
5. Diaz-Gutierrez, P., Bhushan, A., Gopi, M., Pajarola, R.: Single-strips for fast interactive rendering. J. Vis. Comput. 22(6), 372-386 (2006) | |||
6. Dutta, R., Savage, C.: A Note on the Complexity of Converter Placement Supporting Broadcast in WDM Optical Networks. In: Proceedings of the International Conference on Telecommunication Systems-Modeling and Analysis, Dallas, November 2005 ISBN: 0-9716253-3-6 pp. 23-31. American Telecommunication Systems Management Association, Nashville | |||
7. Egecioglu, O., Gonzalez, T.: Minimum-energy Broadcast in Simple Graphs with Limited Node Power. In: Proc. IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2001), Anaheim, August 2001 pp. 334-338 | |||
8. Estivill-Castro, V., Fellows, M.R., Langston, M.A., Rosamond, F.A.: FPT is P-time extremal structure I. In: Algorithms and complexity in Durham 2005.Texts in Algorithmics, vol.4, pp. 1-41. Kings College Publications, London (2005) | |||
9. Fellows, M., Langston, M.: On well-partial-order theory and its applications to combinatorial problems of VLSI design. SIAM J. Discret. Math. 5,117-126 (1992) | |||
10. Fellows, M.: Blow-ups, win/win's and crown rules: some new directions in FPT. In: Proceedings of the 29th Workshop on Graph Theoretic Concepts in Computer Science (WG 2003). Lecture Notes in Computer Science, vol. 2880, pp. 1-12. Springer, Berlin (2003) | |||
11. Fellows, M., McCartin, C., Rosamond, F., Stege, U.: Coordinatized kernels and catalytic reductions: an improved FPT algorithm for max leaf spanning tree and other problems. In: Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (FST-TCS 2000). Lecture Notes in Theoretical Computer Science 1974, pp. 240-251. Springer, Berlin (2000) | |||
12. Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discret. Math. 4,99-106 (1991) | |||
13. Kouider, M., Vestergaard, P.D.: Generalized connected domination in graphs. Discret. Math. Theor. Comput. Sci. (DMTCS) 8, 57-64 (2006) | |||
14. Lu, H.-I., Ravi, R.: Approximating maximum leaf spanning trees in almost linear time. J. Algorithm 29,132-141 (1998) | |||
15. Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Lecture Series in Mathematics and Its Applications, Oxford University Press, Oxford (2006) | |||
16. Prieto-Rodriguez, E.: Systematic kernelization in FPT algorithm design. Dissertation, School of Electrical Engineering and Computer Science, University of Newcastle, Australia (2005) | |||
17. Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with the maximum number of leaves. In: Proceedings of the 6th Annual European Symposium on Algorithms (ESA'98). Lecture Notes in Computer Science, vol. 1461, pp. 441-452. Springer, Berlin (1998) | |||
