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

dmtcs:625 - Discrete Mathematics & Theoretical Computer Science, March 24, 2013, Vol. 15 no. 1 -
Isomorphism of graph classes related to the circular-ones propertyArticle

Authors: Andrew R. Curtis 1; Min Chih Lin ORCID2; Ross M. Mcconnell 3; Yahav Nussbaum 4; Francisco Juan Soulignac 2; Jeremy P. Spinrad 5; Jayme Luiz Szwarcfiter 6

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.

Volume: Vol. 15 no. 1
Section: Discrete Algorithms
Published on: March 24, 2013
Accepted on: June 9, 2015
Submitted on: August 8, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

4 Documents citing this article

Consultation statistics

This page has been seen 406 times.
This article's PDF has been downloaded 505 times.