Seese, D. 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. Cited in 21 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science 05C75 Structural characterization of families of graphs Citations:Zbl 0568.00020 PDFBibTeX XML