@techreport{Report-235-1989,
Title = {Efficient Computations in Tree-Like Graphs},
Author = {Andrzej Proskurowski and Maciej M. Sys\lo},
Year = {1989},
Number = {235},
Type = {Preprint},
Institution = {Technische Universit\"at Berlin, Institut f\"ur Mathematik},
Abstract = {Many discrete optimization problems are both very difficult and important in a range of applications in engineering, computer science and operations research. In recent years, a generally accepted measure of a problem's difficulty became a worst-case, asymptotic growth complexity characterization. Because of the anticipated at least exponential complexity of any solution algorithm for members in the class of $\cal NP$-hard problems, restricted domains of problems' instances are being studied, with hopes that some such modified problems would admit efficient (polynomially bounded) solution algorithms. We survey investigations of the complexity behaviour of $\cal NP$-hard discrete optimization problems on graphs restricted to different generalizations of trees (cycle-free, connected graphs). The scope of this survey includes definitions and algorithmic characterization of families of graphs with tree-like structures that may guide the development of efficient solution algorithms for difficult optimization problems and the development of such solution algorithms.}
}