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

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

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



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






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


Фундамент. и прикл. матем., 2013, том 18, выпуск 2, страницы 105–118 (Mi fpm1502)  

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

Общая грань некоторых $0/1$-многогранников с NP-полным критерием несмежности вершин

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

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

Аннотация: В работе рассматриваются многогранники двойных покрытий. В 1995 г. Мацуи установил, что задача проверки несмежности вершин для этих многогранников NP-полна. Мы покажем, что многогранники двойных покрытий являются гранями многогранников, ассоциированных со следующими задачами: задача о рюкзаке, задача о покрытии множества, задача о кубическом подграфе, задача о $3$-выполнимости, задача о частичном упорядочении, задача коммивояжёра и некоторые другие.

Ключевые слова: NP-полные задачи, многогранники, смежные вершины, грани.

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

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2014, 203:6, 823–832

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

Тип публикации: Статья
УДК: 519.854.2+519.161

Образец цитирования: А. Н. Максименко, “Общая грань некоторых $0/1$-многогранников с NP-полным критерием несмежности вершин”, Фундамент. и прикл. матем., 18:2 (2013), 105–118; J. Math. Sci., 203:6 (2014), 823–832

Цитирование в формате AMSBIB
\RBibitem{Mak13}
\by А.~Н.~Максименко
\paper Общая грань некоторых $0/1$-многогранников с~NP-полным критерием несмежности вершин
\jour Фундамент. и прикл. матем.
\yr 2013
\vol 18
\issue 2
\pages 105--118
\mathnet{http://mi.mathnet.ru/fpm1502}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3431788}
\transl
\jour J. Math. Sci.
\yr 2014
\vol 203
\issue 6
\pages 823--832
\crossref{https://doi.org/10.1007/s10958-014-2172-9}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84922076244}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/fpm1502
  • http://mi.mathnet.ru/rus/fpm/v18/i2/p105

    ОТПРАВИТЬ: 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. A. N. Maksimenko, “A special role of Boolean quadratic polytopes among other combinatorial polytopes”, Модел. и анализ информ. систем, 23:1 (2016), 23–40  mathnet  crossref  mathscinet  elib
    2. А. Н. Максименко, “Сложность задач комбинаторной оптимизации в терминах решëток граней ассоциированных многогранников”, Дискретн. анализ и исслед. опер., 23:3 (2016), 61–80  mathnet  crossref  mathscinet  elib; A. N. Maksimenko, “Complexity of combinatorial optimization problems in terms of face lattice of associated polytopes”, J. Appl. Industr. Math., 10:3 (2016), 370–379  crossref
    3. А. Н. Максименко, “Об одном семействе 0/1-многогранников с NP-полным критерием несмежности вершин”, Дискрет. матем., 29:2 (2017), 29–39  mathnet  crossref  elib
    4. А. Н. Максименко, “Булев квадратичный многогранник является гранью многогранника линейных порядков”, Сиб. электрон. матем. изв., 14 (2017), 640–646  mathnet  crossref
    5. Р. Ю. Симанчëв, “О смежности вершин многогранника связных k-факторов”, Тр. ИММ УрО РАН, 24, № 2, 2018, 235–242  mathnet  crossref  elib
  • Фундаментальная и прикладная математика
    Просмотров:
    Эта страница:120
    Полный текст:38
    Литература:24
    Первая стр.:1

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