Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. (English) Zbl 0651.68079

Bodlaender, Hans L.

Algorithm theory, Proc. 1st Scand. Workshop, Halmstad/Sweden 1988, Lect. Notes Comput. Sci. 318, 223-232 (1988).

Summary: [For the entire collection see Zbl 0639.00043.]
We show that the graph isomorphism and chromatic index problems are solvable in polynomial time when restricted to the class of graphs with treewidth \(\leq k\) (k a constant) (or equivalently, the class of partial k-trees). Also, we show that there exist algorithms that find tree- decompositions with treewidth \(\leq k\) of graphs with treewidth \(\leq k\), in O(n 3) time, (k constant).

MSC:

68R10	Graph theory (including graph drawing) in computer science
68Q25	Analysis of algorithms and problem complexity

Keywords:

graphs with small treewidth; NP-complete; graph isomorphism; chromatic index; polynomial time; partial k-trees; tree-decompositions

Citations:

Zbl 0639.00043