Curtis, Andrew R. and Lin, Min Chih and Mcconnell, Ross M. and Nussbaum, Yahav and Soulignac, Francisco Juanet 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 property

Authors: Curtis, Andrew R. and Lin, Min Chih and Mcconnell, Ross M. and Nussbaum, Yahav and Soulignac, Francisco Juan and Spinrad, Jeremy P. and Szwarcfiter, Jayme Luiz

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.


Source : oai:HAL:hal-00990614v1
Volume: Vol. 15 no. 1
Section: Discrete Algorithms
Published on: March 24, 2013
Submitted on: August 8, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 61 times.
This article's PDF has been downloaded 72 times.