Том 19, номер 1, 2012 г., Стр. 74-96

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

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

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

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

Статья поступила 31 мая 2011 г.
Исправленный вариант — 2 ноября 2011 г.

Литература

[1] Алексеев В. Е., Малышев Д. С. Критерий граничности и его применения // Дискрет. анализ и исслед. операций. — 2008. — T. 15, № 6. — С. 3–10.

[2] Коробицын Д. В. О сложности определения числа доминирования в моногенных классах графов // Дискрет. математика. — 1990. — Т. 2, № 3. — С. 90–96.

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

[4] Малышев Д. С. О минимальных сложных элементах решетки наследственных классов графов // Мат. VII молодёж. научн. школы по дискретной математике и её приложениям (Москва, 18–23 мая 2009 г.), часть II. — М: Изд-во ИПМ РАН, 2009. — С. 12–17.

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

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

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

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

[9] 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.

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

[11] Ding G. Subgraphs and well-quasi-ordering // J. Graph Theory. — 1992. — Vol. 16. — P. 489–502.

[12] Distel R. Graph Theory. — New York: Springer-Verl., 2000. — 322 p.

[13] Kral D., Kratochvil J., Tuza T., Woeginger G. Сomplexity of coloring of graphs without forbidden induced subgraphs // Graph-theoretic concepts in computer science. Proc. 27th Int. Workshop (Boltenhagen, Germany, June 14–16, 2001). — Berlin, Heidelberg: Springer-Verl., 2001. — P. 254–262. (Lect. Notes Comput. Sci.; Vol. 2204.)

[14] Lozin V. V. A decidability results for the dominating set problem // Theor. Comput. Sci. — 2011. — doi: 10.1016/j.tcs.2010.08.027.