2007/01/01 by Vincent Limouzy, Fabien de Montgolfier, Fabien De Montgolfier +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Constraint Satisfaction and Optimization #Graph Theory and Algorithms #cs.DS
paper · pdf · doi:10.1007/978-3-540-74839-7_9
published as 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) · soumis à WG 2007; 12p
openalex publication_date 2007/01/01 · arxiv created 2007/03/03 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/04
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(n2 m)-time algorithm, improving Johansson's algorithm \citeJohansson00. Moreover, our alogrithm is simple to understand. The above properties and algorithm allow us to propose a robust O(n2 m)-time isomorphism algorithm for NLC-2 graphs. As far as we know, it is the first polynomial-time algorithm.