Isomorphism of graph classes related to the circular-ones property

Volver a la Vista simple
dc.conicet.fuenteunificacion
dc.conicet.organizacionUniversity of Waterloo
dc.conicet.organizacionUniversidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo
dc.conicet.organizacionConsejo Nacional de Investigaciones Científicas y Técnicas
dc.conicet.organizacionState University of Colorado - Fort Collins
dc.conicet.organizacionTel Aviv University
dc.conicet.organizacionConsejo Nacional de Investigaciones Científicas y Técnicas
dc.conicet.organizacionUniversidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación
dc.conicet.organizacionVanderbilt University
dc.conicet.organizacionUniversidade Federal do Rio de Janeiro
dc.conicet.paisOrganizacionCanadá
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionEstados Unidos
dc.conicet.paisOrganizacionIsrael
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionEstados Unidos
dc.conicet.paisOrganizacionBrasil
dc.conicet.produccionid7856349
dc.contributor.authorCurtis, Andrew R.
dc.contributor.authorLin, Min Chih
dc.contributor.authorMcConnell, Ross M.
dc.contributor.authorNussbaum, Yahav
dc.contributor.authorSoulignac, Francisco Juan
dc.contributor.authorSpinrad, Jeremy P.
dc.contributor.authorSzwarcfiter, Jayme L.
dc.date.accessioned2019-09-26T15:39:34Z
dc.date.available2019-09-26T15:39:34Z
dc.date.issued2013-03
dc.date.updated2019-09-24T12:52:47Z
dc.description.abstractWe 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.es
dc.description.filFil: Curtis, Andrew R.. University of Waterloo; Canadá
dc.description.filFil: 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.filFil: McConnell, Ross M.. State University of Colorado - Fort Collins; Estados Unidos
dc.description.filFil: Nussbaum, Yahav. Tel Aviv University; Israel
dc.description.filFil: 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.filFil: Spinrad, Jeremy P.. Vanderbilt University; Estados Unidos
dc.description.filFil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil
dc.formatapplication/pdfes
dc.identifier.citationCurtis, 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-182es
dc.identifier.institucionalCONICET
dc.identifier.issn1365-8050es
dc.identifier.repoCONICET Digital
dc.identifier.urihttp://hdl.handle.net/11336/84528
dc.journal.ciudadNancyes
dc.journal.number1es
dc.journal.pagination157-182es
dc.journal.paisFranciaes
dc.journal.titleDiscrete Mathematics and Theoretical Computer Sciencees
dc.journal.volume15es
dc.language.isoenges
dc.publisherDiscrete Mathematics and Theoretical Computer Sciencees
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/url/https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2298.1.html
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1203.4822
dc.rightsinfo:eu-repo/semantics/openAccess*
dc.rights.urihttps://creativecommons.org/licenses/by-nc-sa/2.5/ar/*
dc.subjectcircular-ones propertyes
dc.subjectmatrix isomorphismes
dc.subjectcircular-arc graphses
dc.subjectgraph isomorphismes
dc.subject.classificationCiencias de la Computaciónes
dc.subject.classificationCiencias de la Computación e Informaciónes
dc.subject.classificationCIENCIAS NATURALES Y EXACTASes
dc.subject.classificationMatemática Aplicadaes
dc.subject.classificationMatemáticases
dc.subject.classificationCIENCIAS NATURALES Y EXACTASes
dc.titleIsomorphism of graph classes related to the circular-ones propertyes
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion

Archivos

Bloque original

Miniatura
Nombre:
CONICET_Digital_Nro.6bdfe74a-cbc4-4d73-8ae7-8b308aa85024_A.pdf
Tamaño:
418.13 KB
Formato:
Adobe Portable Document Format
Descargar

Colecciones

Articulos(OCA CIUDAD UNIVERSITARIA)
Volver a la Vista simple