На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

В Институте математики Сибирского федерального университета предложен современный подход к разработке эффективных алгоритмов решения оптимизационных задач на графах ограниченной древовидной ширины

06.03.2012

Многие проблемы реальной жизни, связанные с дискретными объектами, могут быть смоделированы как оптимизационные задачи на графах. К сожалению, подавляющее большинство оптимизационных задач на графах являются NP-трудными и для них не найдено эффективных (полиномиальных по времени) алгоритмов решения. Возможный путь преодоления этой проблемы - выявление классов графов, для которых NP-трудные задачи эффективно разрешимы. Представительный класс подобных графов образуют частичные k-деревья - графы, обладающие ограниченной древовидной шириной [1]. В него входят, например, ациклические, хордальные, последовательно-параллельные графы, графы Халина.

Другая возможность преодоления высокой вычислительной сложности NP-трудных графовых задач - это организация процедуры поиска оптимального решения по принципу «разделяй и властвуй». Для частичных k-деревьев, когда k - положительная целая константа, этот принцип эффективно реализуется методом динамического программирования на основе дерева декомпозиции графа. Сочетание декомпозиционного метода с декомпозиционным представлением входного графа составляет суть одного из современных подходов разработки эффективных алгоритмов решения большого класса важных практических задач, выражаемых на языке теории графов и комбинаторной оптимизации

Подробное описание дается в статье «Программирование задач на графах ограниченной древовидной ширины», автор Быкова В.В. (Институт математики Сибирского федерального университета, г. Красноярск).