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 - https://doi.org/10.46298/dmtcs.625
Isomorphism of graph classes related to the circular-ones property

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

  • 1 David R. Cheriton School of Computer Science
  • 2 Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires]
  • 3 Computer Science Department, Colorado State University
  • 4 School of Computer Science
  • 5 Department of Electrical Engineering & Computer Science [Nashville]
  • 6 Instituto de Matemática da Universidade Federal do Rio de Janeiro

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]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1903.11062
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1903.11062
  • 1903.11062
  • 10.48550/arxiv.1903.11062
Testing isomorphism of circular-arc graphs in polynomial time

2 Documents citing this article

Consultation statistics

This page has been seen 335 times.
This article's PDF has been downloaded 466 times.