Skip to Main content Skip to Navigation
Journal articles

Isomorphism of graph classes related to the circular-ones property

Abstract : We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. Our algorithm is similar to the isomorphism algorithm for interval graphs of Lueker and Booth, but works on PC trees, which are unrooted and have a cyclic nature, rather than with PQ trees, which are rooted. This algorithm leads to linear-time isomorphism algorithms for related graph classes, including Helly circular-arc graphs, Γ circular-arc graphs, proper circular-arc graphs and convex-round graphs.
Document type :
Journal articles
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 4:29:03 PM
Last modification on : Tuesday, October 19, 2021 - 11:03:55 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:42:57 PM


Files produced by the author(s)




Andrew R. Curtis, Min Chih Lin, Ross M. Mcconnell, Yahav Nussbaum, Francisco Juan Soulignac, et al.. Isomorphism of graph classes related to the circular-ones property. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.157--182. ⟨10.46298/dmtcs.625⟩. ⟨hal-00990614⟩



Record views


Files downloads