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 <>
Submitted on : Tuesday, May 13, 2014 - 4:29:03 PM
Last modification on : Monday, October 19, 2020 - 2:34:03 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

  • HAL Id : hal-00990614, version 1

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. ⟨hal-00990614⟩

Share

Metrics

Record views

417

Files downloads

1359