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

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

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



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






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


Дискретн. анализ и исслед. опер., 2013, том 20, номер 6, страницы 59–76 (Mi da753)  

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

Критические классы графов для задачи о рёберном списковом ранжировании

Д. С. Малышевab

a Нац. исслед. университет "Высшая школа экономики", ул. Б. Печёрская, 25/12, 603155 Н. Новгород, Россия
b Нижегородский гос. университет им. Н. И. Лобачевского, пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия

Аннотация: Задача о рёберном списковом ранжировании является обобщением классической задачи о раскраске рёбер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность этой задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определённые и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся совокупность “критических” классов графов, включение которых в конечно определённый класс эквивалентно “труднорешаемости” задачи о рёберном списковом ранжировании в этом классе. По-видимому, это вообще первый результат о полном таком описании для неискусственных NP-полных задач на графах. Конструктивно доказывается, что для этой задачи среди минимальных по включению наследственных случаев “труднорешаемости” имеется всего пять конечно определённых классов и один минорно замкнутый класс. Ил. 1, библиогр. 13.

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

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2014, 8:2, 245–255

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

Тип публикации: Статья
УДК: 519.178
Статья поступила: 06.08.2012
Переработанный вариант: 14.03.2013

Образец цитирования: Д. С. Малышев, “Критические классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 20:6 (2013), 59–76; J. Appl. Industr. Math., 8:2 (2014), 245–255

Цитирование в формате AMSBIB
\RBibitem{Mal13}
\by Д.~С.~Малышев
\paper Критические классы графов для задачи о~рёберном списковом ранжировании
\jour Дискретн. анализ и исслед. опер.
\yr 2013
\vol 20
\issue 6
\pages 59--76
\mathnet{http://mi.mathnet.ru/da753}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3185264}
\transl
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 2
\pages 245--255
\crossref{https://doi.org/10.1134/S1990478914020112}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84902132811}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da753
  • http://mi.mathnet.ru/rus/da/v20/i6/p59

    ОТПРАВИТЬ: 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. D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Сиб. электрон. матем. изв., 11 (2014), 811–822  mathnet
    2. А. В. Ильев, “Разрешимость универсальных теорий и аксиоматизируемость наследственных классов графов”, Тр. ИММ УрО РАН, 22, № 1, 2016, 100–111  mathnet  mathscinet  elib
    3. А. В. Ильев, “Об аксиоматизируемости наследственных классов графов и матроидов”, Сиб. электрон. матем. изв., 13 (2016), 137–147  mathnet  crossref
    4. D. S. Malyshev, “A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs”, Discrete Appl. Math., 203 (2016), 117–126  crossref  mathscinet  zmath  isi  elib  scopus
    5. Д. С. Малышев, “Критические элементы в комбинаторно замкнутых семействах классов графов”, Дискретн. анализ и исслед. опер., 24:1 (2017), 81–96  mathnet  crossref  mathscinet  elib; D. S. Malyshev, “Critical elements in combinatorially closed families of graph classes”, J. Appl. Industr. Math., 11:1 (2017), 99–106  crossref
    6. Д. Б. Мокеев, “О кёниговых графах относительно $P_4$”, Дискретн. анализ и исслед. опер., 24:3 (2017), 61–79  mathnet  crossref  elib; D. B. Mokeev, “On König graphs with respect to $P_4$”, J. Appl. Industr. Math., 11:3 (2017), 421–430  crossref
    7. D. S. Malyshev, O. O. Lobanova, “Two complexity results for the vertex coloring problem”, Discrete Appl. Math., 219 (2017), 158–166  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:228
    Полный текст:37
    Литература:21
    Первая стр.:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019