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

Описание

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

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

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

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

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

Издание

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

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

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

ISSN журнала: 23116749

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

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

Персоны

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