Том 17, номер 1, 2010 г., Стр. 3-10
УДК 519.17
Алексеев В. Е., Захарова Д. В.
Независимые множества в графах с ограниченными минорами расширенной матрицы инцидентности
Аннотация:
Характеризуются графы, у которых абсолютные величины миноров расширенной матрицы инцидентности ограничены сверху некоторой константой. Доказывается, что при любом фиксированном k задача о независимом множестве решается за полиномиальное время для графов, у которых абсолютные величины миноров матрицы, полученной из матрицы инцидентности добавлением столбца из единиц, не превосходят k.
Библиогр. 6.
Ключевые слова: расширенная матрица инцидентности, минор, задача о независимом множестве.
Алексеев Владимир Евгеньевич 1
Захарова Дарья Владимировна 1
1. Нижегородский гос. университет,
пр. Гагарина, 23, корп. 2, 603950 Нижний Новгород, Россия
е-mail: ave@uic.nnov.ru
Статья поступила 2 марта 2009 г.
