NLC-2 graph recognition and isomorphism
| dc.creator | Limouzy, Vincent | |
| dc.creator | De Montgolfier, Fabien | |
| dc.creator | Rao, Michaël | |
| dc.date | 2007-03-03 | |
| dc.date.accessioned | 2026-07-07T08:48:23Z | |
| dc.date.available | 2026-07-07T08:48:23Z | |
| dc.description | 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. | |
| dc.description | soumis à WG 2007; 12p | |
| dc.identifier | https://arxiv.org/abs/cs/0703013 | |
| dc.identifier | http://arxiv.org/abs/cs/0703013 | |
| dc.identifier | 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) | |
| dc.identifier | doi:10.1007/978-3-540-74839-7_9 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/143929 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | NLC-2 graph recognition and isomorphism | |
| dc.type | text |