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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 1 (1), pp.157--182
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990614
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 16:29:03
Dernière modification le : mardi 24 avril 2018 - 11:24:01
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:42:57

Fichier

2298-7800-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

194