Polynomial-time algorithm for isomorphism of graphs with clique-width at most three

Publications

Polynomial-time algorithm for isomorphism of graphs with clique-width at most three

Year : 2016

Publisher : Springer Verlagservice@springer.de

Source Title : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Document Type :

Abstract

The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism algorithm for graphs with clique-width at most three. Our work is independent of the work by Grohe and Schweitzer [17] showing that the isomorphism problem for graphs of bounded cliquewidth is polynomial time.