Dynamic programming and graph optimization problems

AbstractSeveral classes of graph optimization problems, which can be solved using dynamic programming, are known to have more efficient tailor-made algorithms. This paper discusses four such classes and the underlying constraints on their subproblem interrelationships that yield these efficient algorithms. These classes are also extended to handle more general cost functions