RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. ИММ УрО РАН, 2018, том 24, номер 2, страницы 235–242 (Mi timm1538)  

О смежности вершин многогранника связных k-факторов

Р. Ю. Симанчёвab

a Омский государственный университет им. Ф. М. Достоевского
b Омский научный центр СО РАН

Аннотация: Комбинаторные характеристики многогранников, ассоциированных с комбинаторными задачами оптимизации, в определенной степени могут считаться характеристиками их труднорешаемости. Например, $NP$-полнота проверки несмежности вершин многогранника задачи очень часто сопутствует $NP$-трудности самой задачи. Еще одной важной характеристикой графа многогранника задачи является кликовое число. В некотором довольно широком классе алгоритмов кликовое число является нижней оценкой временной трудоемкости задачи. Кроме того, для большого количества труднорешаемых задач известны экспоненциальные нижние оценки кликового числа графов многогранников, в то время как для полиномиально разрешимых задач для него установлены полиномиальные нижние и верхние оценки. В данной работе рассматривается многогранник задачи о взвешенном связном остовном $k$-однородном подграфе (связном $k$-факторе) полного $n$-вершинного графа, который при $k=2$ является многогранником симметричной задачи коммивояжера. Показано, что при $k$, удовлетворяющих условиям $k\geq 3$ и ${\displaystyle{\lceil \frac{k}{2} \rceil \leq \frac{n}{8} - 1}}$, проверка несмежности вершин этого многогранника является $NP$-полной задачей и кликовое число экспоненциально по $n$. Доказательства основаны на сведении к случаю $k=2$.

Ключевые слова: k-фактор, многогранник, смежность вершин многогранника, кликовое число графа.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-07-00599
Работа выполнена при поддержке РФФИ (проект 18-07-00599).


DOI: https://doi.org/10.21538/0134-4889-2018-24-2-235-242

Полный текст: PDF файл (190 kB)
Первая страница: PDF файл
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.85
MSC: 90XXX
Поступила в редакцию: 05.02.2018

Образец цитирования: Р. Ю. Симанчëв, “О смежности вершин многогранника связных k-факторов”, Тр. ИММ УрО РАН, 24, № 2, 2018, 235–242

Цитирование в формате AMSBIB
\RBibitem{Sim18}
\by Р.~Ю.~Симанч\"eв
\paper О смежности вершин многогранника связных k-факторов
\serial Тр. ИММ УрО РАН
\yr 2018
\vol 24
\issue 2
\pages 235--242
\mathnet{http://mi.mathnet.ru/timm1538}
\crossref{https://doi.org/10.21538/0134-4889-2018-24-2-235-242}
\elib{http://elibrary.ru/item.asp?id=35060693}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timm1538
  • http://mi.mathnet.ru/rus/timm/v24/i2/p235

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды Института математики и механики УрО РАН
    Просмотров:
    Эта страница:8
    Литература:1

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018