Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
Source
Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics
ISSN
03029743
Date Issued
2016-01-01
Author(s)
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.