TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1989

COGA 5-Wheel


zur Navigation

Preprints 1989

Efficient Computations in Tree-Like Graphs
Zitatschlüssel Report-235-1989
Autor Andrzej Proskurowski and Maciej M. Sysło
Jahr 1989
Nummer 235
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe