DYNAMIC-PROGRAMMING AND GRAPH OPTIMIZATION PROBLEMS

Authors
HU TC MORGENTHALER JD
Citation
Tc. Hu et Jd. Morgenthaler, DYNAMIC-PROGRAMMING AND GRAPH OPTIMIZATION PROBLEMS, Computers & mathematics with applications, 27(9-10), 1994, pp. 53-58
Citations number
39
Categorie Soggetti
Computer Sciences",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications → ACNP
ISSN journal
08981221
Volume
27
Issue
9-10
Year of publication
1994
Pages
53 - 58
Database
ISI
SICI code
0898-1221(1994)27:9-10<53:DAGOP>2.0.ZU;2-#
Abstract
Several classes of graph optimization problems, which can be solved us ing 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 ef ficient algorithms. These classes are also extended to handle more gen eral cost functions.