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

https://hal.inria.fr/hal-00990614
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

File

2298-7800-2-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

156

Files downloads

766