Тип публикации: статья из журнала
Год издания: 2016
Ключевые слова: двухфазные алгоритмы, предобработка, атомарное разложение, древовидная ширина, оптимизация на графах
Аннотация: Рассматривается декомпозиционный подход, приводящий к ускорению работы классических алгоритмов решения оптимизационных задач на разреженных графах большой размерности. Подход основан на разложении исходного графа на атомы кликовыми минимальными сепараторами. Разреженность графа выражается ограничением на древовидную ширину графа. ППоказать полностьюредставлены алгоритмы и программы, реализующие атомарное разложение графа. Демонстрируется практическое применение данного подхода к NP-трудной задаче о клике.
Журнал: Программные продукты, системы и алгоритмы
Выпуск журнала: № 2
Номера страниц: 3
ISSN журнала: 23116749
Место издания: Тверь
Издатель: Закрытое акционерное общество Научно-исследовательский институт Центрпрограммсистем