О СОВМЕСТИМОСТИ ТРИАНГУЛЯЦИЙ И ГЕОМЕТРИЧЕСКИХ ГРАФОВ
Аннотация
В данной работе найдены универсальные множества точек на плоскости для совместимых триангуляций; показано, что граф дизъюнктно совместимых совершенных паросочетаний, вообще говоря, не является связным; доказано, что произвольное совершенное паросочетание обладает дизъюнктно-совместимым остовным деревом.
При поддержке: Институт математики НАН Беларуси; Белорусский РФФИ
Об авторе
В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси, Минск
Беларусь
Беларусь
Список литературы
1. KrasserH. // Master Thesis, Institute for Theoretical Computer Science, Graz University of Technology. Graz, Austria, 1999.
2. SaarfeldA. // Proc. 3-rd Ann. ACM Sympos. Comput. Geometry. 1987. P. 195-204.
3. Garaa A., Tejel J. // Actas VI Encuentros de Geometria Computational. Barcelona, 1995. P. 169-174.
4. Handbook of Discrete and Computational Geometry/ ed. by J. Goodman and O’Rourke. CRC Press, 1997. Vol. 211.
5. Ishaque M, Souvaine D. L., Toth C. D. // Proc. 27th Annual Symp. On Comput. Geometry. Paris, 2011.
6. Aichholzer O., Bereg S., Dumitrescu A. et al. // Comp. Geometry. 2009. N 42. P. 161-167.
7. Houle M. E., Hurtado F., Noy M, Rivera-Campo E. // Graphs Combin. 2005. Vol. 21, N 3. P. 325-331.
8. Cerny J., Dvorak Z., Jelmek V., Kara J. // Discrete Applied Mathematics. 2007. Vol. 115, N 9. P. 1096-1105.
9. Lee D. T., Lin A. K. // Discrete Comput. Geom. 1986. Vol. 1. P. 201-217.
Рецензия
Просмотров: 777
Послать статью по эл. почте 