НЕПЕРЕСЕКАЮЩИЕСЯ КОНФИГУРАЦИИ В ДОПОЛНЕНИЯХ ГЕОМЕТРИЧЕСКИХ ГРАФОВ И ДИЗЪЮНКТНАЯ СОВМЕСТИМОСТЬ
Аннотация
В работе для произвольного непересекающегося совершенного паросочетания за время O(n4 log n) строится дизъюнктно совместимое остовное дерево максимальной степени вершин не больше 4. Получен критерий существования непересекающегося совершенного паросочетания в дополнении звезды порядка меньше 2n в K2n. Доказано существование непересекающегося совершенного паросочетания в дополнении дерева порядка (n + 1) в K2n с числом внутренних вершин, не превышающим (n – 1).
Список литературы
1. Ishaque, M. Disjoint compatible geometric matchings / M. Ishaque, D. L. Souvaine, C. D. Tóth // Proceedingsof the 27th Symposium on Computational Geometry (Paris, 2011). – New York, 2011. – P. 125–134.
2. Bose, P. Growing a tree from its branches / P. Bose, G. T. Toussaint, // J. Algorithm. – 1995. – Vol. 19, N 1. – P. 86–103.
3. Bose, P. Every set of disjoint segments admits a binary tree / P. Bose, M. E. Houle, G. T. Toussaint // Discr. Comput. Geom. – 2001. – Vol. 26, N 3. – P. 387–410.
4. Hoffmann, M. Pointed binary encompassing trees: simple and optimal / M. Hoffmann, C. D. Toth // Comput. Geom. Theor. Appl. – 2010. – Vol. 43, N 1. – P. 35–41.
5. Souvaine, D. L. A vertex- face assignment for plane graphs / D. L. Souvaine, C. D. Tóth, // Comp. Geom. Theor. Appl. – 2009. – Vol. 42, N 5. – P. 388–394.
6. Rappaport, D. Computing simple circuits from a set of line segments is NP-complete / D. Rappaport // SIAM J. Comput. – 1989. – Vol. 18, N 6. – P. 1128–1139.
7. Compatible geometric matchings / O. Aichholzer [et al.] // Comp. Geom. Theor. Appl. – 2009. – Vol. 42. – P. 617–626.
8. Convex partitions with 2-edge connected dual graphs / M. Al-Jubeh [et al.] // J. Combin. Opt. – 2011. – Vol. 22, N 3. – P. 409–425.
9. Edge-removal and non-crossing configurations in geometric graphs / O. Aichholzer [et al.] // Discr. Math. Theor. Comput. Sci. – 2010. – Vol. 12, N 1. – P. 75–86.
Рецензия
Просмотров: 657
Послать статью по эл. почте 