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

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

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



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Дискретн. анализ и исслед. опер., 2011, том 18, номер 3, страницы 76–83 (Mi da655)  

Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

Многогранники задачи о выполнимости являются гранями многогранника задачи коммивояжёра

А. Н. Максименко

Ярославский гос. университет им. П. Г. Демидова, Ярославль, Россия

Аннотация: Пусть на множестве булевых переменных $U=\{u_1,u_2,…,u_d\}$ задана булева формула $C$ в конъюнктивной нормальной форме. Обозначим через $Y\subset\mathbb R^d$ множество характеристических векторов всех выполняющих $C$ наборов значений переменных. Многогранником задачи о выполнимости $S(U,C)$ назовём выпуклую оболочку множества $Y$. Многогранник коммивояжёра для орграфа на $n$ вершинах обозначим через $T_n$. Показано, что $S(U,C)$ аффинно эквивалентен некоторой грани многогранника $T_n$, где $n=|U|+2\operatorname{len}(C)$, $\operatorname{len}(C)$ – длина формулы $C$ в литералах. Ил. 1, библиогр. 9.

Ключевые слова: многогранник коммивояжёра, многогранник задачи о выполнимости, грань.

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

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.85
Статья поступила: 19.07.2010
Переработанный вариант: 15.03.2011

Образец цитирования: А. Н. Максименко, “Многогранники задачи о выполнимости являются гранями многогранника задачи коммивояжёра”, Дискретн. анализ и исслед. опер., 18:3 (2011), 76–83

Цитирование в формате AMSBIB
\RBibitem{Mak11}
\by А.~Н.~Максименко
\paper Многогранники задачи о~выполнимости являются гранями многогранника задачи коммивояж\"ера
\jour Дискретн. анализ и исслед. опер.
\yr 2011
\vol 18
\issue 3
\pages 76--83
\mathnet{http://mi.mathnet.ru/da655}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2883749}
\zmath{https://zbmath.org/?q=an:1249.90327}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da655
  • http://mi.mathnet.ru/rus/da/v18/i3/p76

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. А. Н. Максименко, “Аналог теоремы Кука для многогранников”, Изв. вузов. Матем., 2012, № 8, 34–42  mathnet  mathscinet; A. N. Maksimenko, “An analog of the Cook theorem for polytopes”, Russian Math. (Iz. VUZ), 56:8 (2012), 28–34  crossref
    2. А. В. Селиверстов, “О мономах квадратичных форм”, Дискретн. анализ и исслед. опер., 20:3 (2013), 65–70  mathnet  mathscinet; A. V. Seliverstov, “On monomials in quadratic forms”, J. Appl. Industr. Math., 7:3 (2013), 431–434  crossref
    3. А. Н. Максименко, “$k$-смежностные грани булева квадратичного многогранника”, Фундамент. и прикл. матем., 18:2 (2013), 95–103  mathnet  mathscinet; A. N. Maksimenko, “$k$-neighborly faces of the Boolean quadric polytopes”, J. Math. Sci., 203:6 (2014), 816–822  crossref
    4. A. N. Maksimenko, “A special role of Boolean quadratic polytopes among other combinatorial polytopes”, Модел. и анализ информ. систем, 23:1 (2016), 23–40  mathnet  crossref  mathscinet  elib
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:341
    Полный текст:61
    Литература:32
    Первая стр.:4
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019