Модификация метода динамического программирования в задачах Штейнера на ориентированных графах

  • И.В. Романовский
  • Д.А. Ейбоженко
Keywords: задача Штейнера, ориентированный граф, динамическое программирование, функция Беллмана, приближенные алгоритмы

Abstract

Задача Штейнера на ориентированных графах – наиболее общая в семействе задач Штейнера. Известно, что она является NP-полной. Существует алгоритм для точного решения задачи, основанный на динамическом программировании, пригодный для задач маленького размера. В нашей статье приводятся специальные типы задач, на которых с помощью модификации названного метода точное решение может быть получено за полиномиальное время. Кроме того, представлен метод, предназначенный для приближенного решения произвольных задач Штейнера на ориентированных графах.
Published
2014-01-22
How to Cite
Романовский, И., & Ейбоженко, Д. (2014). Модификация метода динамического программирования в задачах Штейнера на ориентированных графах. Computer Tools in Education, (5). Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1234
Section
Articles