Artículo

Isomorphism of graph classes related to the circular-ones property

Curtis, Andrew R.; Lin, Min ChihIcon ; McConnell, Ross M.; Nussbaum, Yahav; Soulignac, Francisco JuanIcon ; Spinrad, Jeremy P.; Szwarcfiter, Jayme L.
Fecha de publicación: 03/2013
Editorial: Discrete Mathematics and Theoretical Computer Science
Revista: Discrete Mathematics and Theoretical Computer Science
ISSN: 1365-8050
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

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, $Gamma$ circular-arc graphs, proper circular-arc graphs and convex-round graphs.
Palabras clave: circular-ones property , matrix isomorphism , circular-arc graphs , graph isomorphism
 
Archivos asociados
Thumbnail
 
Tamaño: 418.1Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/84528
URL: https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2298.1.html
URL: https://arxiv.org/abs/1203.4822
Colecciones
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Curtis, Andrew R.; Lin, Min Chih; McConnell, Ross M.; Nussbaum, Yahav; Soulignac, Francisco Juan; et al.; Isomorphism of graph classes related to the circular-ones property; Discrete Mathematics and Theoretical Computer Science; Discrete Mathematics and Theoretical Computer Science; 15; 1; 3-2013; 157-182
Compartir