Mostrar el registro sencillo del ítem

dc.contributor.author
Curtis, Andrew R.  
dc.contributor.author
Lin, Min Chih  
dc.contributor.author
McConnell, Ross M.  
dc.contributor.author
Nussbaum, Yahav  
dc.contributor.author
Soulignac, Francisco Juan  
dc.contributor.author
Spinrad, Jeremy P.  
dc.contributor.author
Szwarcfiter, Jayme L.  
dc.date.available
2019-09-26T15:39:34Z  
dc.date.issued
2013-03  
dc.identifier.citation
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  
dc.identifier.issn
1365-8050  
dc.identifier.uri
http://hdl.handle.net/11336/84528  
dc.description.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, $Gamma$ circular-arc graphs, proper circular-arc graphs and convex-round graphs.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Discrete Mathematics and Theoretical Computer Science  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
circular-ones property  
dc.subject
matrix isomorphism  
dc.subject
circular-arc graphs  
dc.subject
graph isomorphism  
dc.subject.classification
Ciencias de la Computación  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.subject.classification
Matemática Aplicada  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Isomorphism of graph classes related to the circular-ones property  
dc.type
info:eu-repo/semantics/article  
dc.type
info:ar-repo/semantics/artículo  
dc.type
info:eu-repo/semantics/publishedVersion  
dc.date.updated
2019-09-24T12:52:47Z  
dc.journal.volume
15  
dc.journal.number
1  
dc.journal.pagination
157-182  
dc.journal.pais
Francia  
dc.journal.ciudad
Nancy  
dc.description.fil
Fil: Curtis, Andrew R.. University of Waterloo; Canadá  
dc.description.fil
Fil: Lin, Min Chih. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina  
dc.description.fil
Fil: McConnell, Ross M.. State University of Colorado - Fort Collins; Estados Unidos  
dc.description.fil
Fil: Nussbaum, Yahav. Tel Aviv University; Israel  
dc.description.fil
Fil: Soulignac, Francisco Juan. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina  
dc.description.fil
Fil: Spinrad, Jeremy P.. Vanderbilt University; Estados Unidos  
dc.description.fil
Fil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil  
dc.journal.title
Discrete Mathematics and Theoretical Computer Science  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2298.1.html  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1203.4822  

Archivos asociados
Thumbnail
 
Tamaño: 418.1Kb
Formato: PDF
.