NLC-2 graph recognition and isomorphism

Details NLC-2 graph recognition and isomorphism NLC-2 graph recognition and isomorphism

2007-03-03

arxiv.org/abs/cs/0703013v1

Dans Lecture Notes In Computer Science - Graph-Theoretic Concepts in Computer Science 33rd International Workshop, WG 2007, Do

Computer Science

Data Structures and Algorithms

soumis \`{a} WG 2007; 12p

Scientific paper

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

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.

Affiliated with

Also associated with

No associations

Rating

NLC-2 graph recognition and isomorphism does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with NLC-2 graph recognition and isomorphism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NLC-2 graph recognition and isomorphism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-719915