RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Института математики и механики УрО РАН // Архив

Тр. ИММ УрО РАН, 2017, том 23, номер 3, страницы 74–81 (Mi timm1438)

Эта публикация цитируется в 2 статьях

Точный алгоритм решения внешнепланарной задачи размещения с улучшенной временной сложностью

Э. Х. Гимади

Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск

Аннотация: Рассматривается сетевая задача размещения с неограниченными объемами производства. В общем случае задача $NP$-трудна. Известно, что задача точно решается с квадратичной трудоемкостью на древовидной сети. В статье исследуется случай сети, представляемой внешнепланарным графом, т. е. графом, все вершины которого принадлежат одной (внешней) грани. Для точного решения рассматриваемой задачи был известен алгоритм с временной сложностью $O(n m^3)$, где $n$ — число вершин, $m$ — число возможных мест размещения предприятий. При использовании некоторых свойств внешнепланарных графов (бинарных 2-деревьев) и учете существования оптимального решения с совокупностью центрально связных областей обслуживания получены рекуррентные соотношения, позволяющие построить точный алгоритм, решающий задачу с уменьшенной в $\sqrt{m}$ раз временной сложностью.

Ключевые слова: задача размещения, сеть, внешнепланарный граф, точный алгоритм, временная сложность, связность.

УДК: 519.85

MSC: 90B80, 90C10, 90C39, 05C10

Поступила в редакцию: 16.05.2017

DOI: 10.21538/0134-4889-2017-23-3-74-81


 Англоязычная версия: Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2018, 303, suppl. 1, 87–93

Реферативные базы данных:


© МИАН, 2024