Тип публикации: статья из журнала
Год издания: 2016
Ключевые слова: разреженные графы, декомпозиция графа, атом графа, предобработка, двухфазные алго-ритмы, древовидная ширина.
Аннотация: Рассматривается NP-трудная задача нахождения наибольшей клики графа (Max-imum Clique Problem, MCP). Предлагается двухфазный алгоритм нахождения точного решения MCP для разреженного графа. Первая фаза алгоритма — предобработка входного графа путем разложения его на атомы, а вторая фаза — применение к каждому атому классического алгоПоказать полностьюритма Уилфа и формирование решения для графа в целом. Уровень разреженности графа задается в виде ограничения на его древовидную ширину. Показано, что время выполнения предлагаемого алгоритма полиномиально зависит от числа вершин и экспоненциально от древовидной ширины графа. Это позволяет применять данный алгоритм к графам большой размерности и малой древовидной ширины.
Журнал: Молодой ученый
Выпуск журнала: № 3
Номера страниц: 4-8
ISSN журнала: 20720297
Место издания: Казань
Издатель: Общество с ограниченной ответственностью Издательство Молодой ученый