Для обыкновенного графа улучшены достаточные условия для того, чтобы равенство числа вершинной независимости и минимальной размерности ортонормального помечиваания влекло равенство числа вершинной независимости и минимального размера кликового покрытия. Для формулировки этого условия рассмотрен класс графов имеющих определенную структуру. Рассмотрена степень улучшения условий.
Original languageRussian
Pages (from-to)90-103
JournalВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. СЕРИЯ 10: ПРИКЛАДНАЯ МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ
Issue number1
StatePublished - 2014

ID: 5688546