Isomorphism of graph classes related to the circular-ones property

Andrew R. Curtis; Francisco J. Soulignac; Jayme L. Szwarcfiter; Jeremy P. Spinrad; Min Chih Lin; Ross M. McConnell; Yahav Nussbaum

arxiv: 1203.4822 · v1 · pith:W5RY6FO6new · submitted 2012-03-21 · 💻 cs.DS · cs.DM

Isomorphism of graph classes related to the circular-ones property

Andrew R. Curtis , Min Chih Lin , Ross M. McConnell , Yahav Nussbaum , Francisco J. Soulignac , Jeremy P. Spinrad , Jayme L. Szwarcfiter This is my paper

classification 💻 cs.DS cs.DM

keywords graphsisomorphismalgorithmcircular-arccircular-onesclassesgraphlinear-time

0 comments

read the original abstract

We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. This algorithm leads to linear-time isomorphism algorithms for related graph classes, including Helly circular-arc graphs, \Gamma-circular-arc graphs, proper circular-arc graphs and convex-round graphs.

This paper has not been read by Pith yet.

Isomorphism of graph classes related to the circular-ones property

discussion (0)