Декомпозиционный подход при решении оптимизационных задач на больших разреженных графах : научное издание

Тип публикации: статья из журнала

Год издания: 2016

Ключевые слова: двухфазные алгоритмы, предобработка, атомарное разложение, древовидная ширина, оптимизация на графах

Аннотация: Рассматривается декомпозиционный подход, приводящий к ускорению работы классических алгоритмов решения оптимизационных задач на разреженных графах большой размерности. Подход основан на разложении исходного графа на атомы кликовыми минимальными сепараторами. Разреженность графа выражается ограничением на древовидную ширину графа. Представлены алгоритмы и программы, реализующие атомарное разложение графа. Демонстрируется практическое применение данного подхода к NP-трудной задаче о клике.

Ссылки на полный текст

Издание

Журнал: Программные продукты, системы и алгоритмы

Выпуск журнала: № 2

Номера страниц: 3

ISSN журнала: 23116749

Место издания: Тверь

Издатель: Закрытое акционерное общество Научно-исследовательский институт Центрпрограммсистем

Персоны

Вхождение в базы данных

РИНЦ (eLIBRARY.RU)

Информация о публикациях загружается с сайта службы поддержки публикационной активности СФУ. Сообщите, если заметили неточности.