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

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

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


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




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

Дискретный анализ и исследование операций, 2013, том 20, выпуск 6, страницы 59–76 (Mi da753)  
Эта публикация цитируется в 19 научных статьях (всего в 19 статьях)

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

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

a Нац. исслед. университет "Высшая школа экономики", ул. Б. Печёрская, 25/12, 603155 Н. Новгород, Россия
b Нижегородский гос. университет им. Н. И. Лобачевского, пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
PDF полного текста (290 kB) Список цитирования (19)
Список литературы:
PDF
HTML
Аннотация: Задача о рёберном списковом ранжировании является обобщением классической задачи о раскраске рёбер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность этой задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определённые и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся совокупность “критических” классов графов, включение которых в конечно определённый класс эквивалентно “труднорешаемости” задачи о рёберном списковом ранжировании в этом классе. По-видимому, это вообще первый результат о полном таком описании для неискусственных NP-полных задач на графах. Конструктивно доказывается, что для этой задачи среди минимальных по включению наследственных случаев “труднорешаемости” имеется всего пять конечно определённых классов и один минорно замкнутый класс. Ил. 1, библиогр. 13.
Ключевые слова: вычислительная сложность, наследственный класс, граничный класс, минимальный сложный класс, полиномиальный алгоритм, задача о рёберном списковом ранжировании.
Статья поступила: 06.08.2012
Переработанный вариант: 14.03.2013
Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2014, Volume 8, Issue 2, Pages 245–255
DOI: https://doi.org/10.1134/S1990478914020112
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.178
Образец цитирования: Д. С. Малышев, “Критические классы графов для задачи о рёберном списковом ранжировании”, Дискретн. анализ и исслед. опер., 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://mathscinet.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{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84902132811}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/da753
  • https://www.mathnet.ru/rus/da/v20/i6/p59
    • Эта публикация цитируется в следующих 19 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дискретный анализ и исследование операций
    Статистика просмотров:
    Страница аннотации:372
    PDF полного текста:99
    Список литературы:46
    Первая страница:2
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024