Modifications of dynamic programming method for Steiner problem in oriented graphs

Abstract

Steiner tree problem on oriented graphs is the most general in the family of Steiner tree problems. It is known to be NP-complete. There exists an algorithm to find an exact solution, based on dynamic programming, but applicable only for problems of modest size. Here special types of problems are presented, for which this algorithm is modified to find exact solution at polynomial time. Also approximate method, based on this algorithm for solving arbitrary problems is produced.