Том 20, номер 6, 2013 г., Стр. 59-76

УДК 519.178
Малышев Д. С.
Критические классы графов для задачи о рёберном списковом ранжировании

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

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

Малышев Дмитрий Сергеевич ^1,2
1. Нац. исслед. университет «Высшая школа экономики»,
ул. Б. Печёрская, 25/12, 603155 Н. Новгород, Россия
Нижегородский гос. университет им. Н. И. Лобачевского,
пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: dsmalyshev@rambler.ru

Статья поступила 6 августа 2012 г.
Исправленный вариант — 14 марта 2013 г.

Литература

[1] Малышев Д. С. О минимальных сложных элементах решетки наследственных классов графов // Мат. VII молодеж. науч. школы по дискрет. математике и её прил. - М: Изд-во ИПМ РАН. - С. 12–17.

[2] Малышев Д. С. О минимальных сложных классах графов // Дискрет. анализ и исслед. операций. - 2009. - T. 16, № 6. - С. 43–51.

[3] Малышев Д. С. Исследование границ эффективной разрешимости в семействе наследственных классов графов: Дисс. . . . канд. физ.–мат. наук: 01.01.09. - Нижний Новгород, 2009. - 113 c.

[4] Малышев Д. С. Последовательные минимумы решётки наследственных классов графов для задачи о рёберном списковом ранжировании // Вестн. Нижегородск. ун-та им. Н. И. Лобачевского. - 2010. - № 4. - С. 133–136.

[5] Малышев Д. С. Минимальные сложные классы для задачи о рёберном списковом ранжировании // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 1. - С. 70–76.

[6] Малышев Д. С., Алексеев В. Е. Граничные классы для задач о списковом ранжировании относительно лесов // Дискрет. анализ и исслед. операций. - 2011. - Т. 18, № 6. - С. 61–70.

[7] Малышев Д. С. Анализ сложности задачи о рёберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 1. - С. 74–96.

[8] Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math. - 2004. - Vol. 132. - P. 17–26.

[9] Dereniowski D. Edge ranking of weighted trees // Discrete Appl. Math. - 2006. - Vol. 154. - P. 1198–1209.

[10] Dereniowski D. The complexity of list ranking of trees // Ars Comb. - 2008. - Vol. 86. - P. 97–114.

[11] Leiserson C. Area-efficient graph layout (for VLSI) // Proc. 21st Ann. IEEE Symp. Foundations of Computer Science. - Syracuse: IEEE, 1980. - P. 270–281.

[12] Liu J. The role of elimination trees in sparse factorization // SIAM J. Matrix Anal. Appl. - 1990. - Vol. 11. - P. 134–172.

[13] Makino K., Uno Y., Ibaraki T. Minimum edge ranking spanning trees of threshold graphs // Lect. Notes Comput. Sci. - 2002. - Vol. 2518. - P. 428–440.