zbMATH — the first resource for mathematics

Tree-partite graphs and the complexity of algorithms. (English) Zbl 0574.68036
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 412-421 (1985).
[For the entire collection see Zbl 0568.00020.]
A lot of algorithmic problems in graph theory are NP-hard and have (at least till now) no solutions in polynomial time. Many of them remain even NP-hard if they are restricted to smaller and simpler classes of graphs. But if the regarded class of graphs is very simple, as for instance the class of trees, or the class of series-parallel graphs, then some of the NP-hard problems have solutions in polynomial or even in linear time. This suggests the problem to find a structural reason for this behaviour of these algorithmic problems. The present paper tries to give a partial answer to this problem.

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
05C75 Structural characterization of families of graphs