NLC-2 graph recognition and isomorphism

Vincent Limouzy; Fabien De Montgolfier; Michaël Rao

doi:10.1007/978-3-540-74839-7_9

paper

NLC-2 graph recognition and isomorphism

arXiv:cs/0703013 · doi:10.1007/978-3-540-74839-7_9

Abstract

NLC-width is a variant of clique-width with many application in graph algorithmic. This paper is devoted to graphs of NLC-width two. After giving new structural properties of the class, we propose a $O (n^{2} m)$ -time algorithm, improving Johansson's algorithm \cite{Johansson00}. Moreover, our alogrithm is simple to understand. The above properties and algorithm allow us to propose a robust $O (n^{2} m)$ -time isomorphism algorithm for NLC-2 graphs. As far as we know, it is the first polynomial-time algorithm.

soumis à WG 2007; 12p