Ссылки

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

    Области исследований

  • граф, ортонормальное помечивание, ранг, минимальный ранг, симметричные матрицы, клика, независимое множество, минимальный размер кликового покрытия, число вершинной независимости, минимальная размерность ортонормального помечивания.

ID: 5688546