Preview

Доклады Национальной академии наук Беларуси

Расширенный поиск

НЕПЕРЕСЕКАЮЩИЕСЯ КОНФИГУРАЦИИ В ДОПОЛНЕНИЯХ ГЕОМЕТРИЧЕСКИХ ГРАФОВ И ДИЗЪЮНКТНАЯ СОВМЕСТИМОСТЬ

Полный текст:

Аннотация

В работе для произвольного непересекающегося совершенного паросочетания за время 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.


Просмотров: 357


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-8323 (Print)
ISSN 2524-2431 (Online)