| Article ID: | iaor20001082 |
| Country: | United States |
| Volume: | 27 |
| Issue: | 9/10 |
| Start Page Number: | 53 |
| End Page Number: | 58 |
| Publication Date: | Sep 1994 |
| Journal: | Computers & Mathematics with Applications |
| Authors: | Hu T.C., Morgenthaler J.D. |
| Keywords: | graphs |
Several 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.