NLC-2 graph recognition and isomorphism
<|reference_start|>NLC-2 graph recognition and isomorphism: 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.<|reference_end|>
@article{limouzy2007nlc-2,
    title={NLC-2 graph recognition and isomorphism},
    author={Vincent Limouzy (LIAFA), Fabien De Montgolfier (LIAFA), Micha"el Rao
  (LIAFA)},
    journal={Dans Lecture Notes In Computer Science - Graph-Theoretic Concepts
  in Computer Science 33rd International Workshop, WG 2007, Dornburg, Germany,
  June 21-23, 2007., Dornburg : Allemagne (2007)},
    year={2007},
    doi={10.1007/978-3-540-74839-7_9},
    archivePrefix={arXiv},
    eprint={cs/0703013},
    primaryClass={cs.DS}
}