Mostrar el registro sencillo del ítem
dc.contributor.author
Safe, Martin Dario
dc.date.available
2021-09-06T16:04:33Z
dc.date.issued
2021-04-12
dc.identifier.citation
Safe, Martin Dario; Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs; Society for Industrial and Applied Mathematics; Siam Journal On Discrete Mathematics; 35; 2; 12-4-2021; 707-751
dc.identifier.issn
0895-4801
dc.identifier.uri
http://hdl.handle.net/11336/139699
dc.description.abstract
In 1969, Tucker characterized proper circular-arc graphs as those graphs whose augmented adjacency matrices have the circularly compatible ones property. Moreover, he also found a polynomial-time algorithm for deciding whether any given augmented adjacency matrix has the circularly compatible ones property. These results led to the first polynomial-time recognition algorithm for proper circular-arc graphs. However, as remarked there, this work did not solve the problems of finding a structure theorem and an efficient recognition algorithm for the circularly compatible ones property in arbitrary matrices (i.e., not restricted to augmented adjacency matrices only). In the present work, we solve these problems. More precisely, we give a minimal forbidden submatrix characterization for the circularly compatible ones property in arbitrary matrices and a linear-time recognition algorithm for the same property. We derive these results from analogous ones for the related $D$-circular property. Interestingly, these results lead to a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for proper circular-arc bigraphs, solving a problem first posed by Basu et al. [J. Graph Theory, 73 (2013), pp. 361--376]. Our findings generalize some known results about $D$-interval hypergraphs and proper interval bigraphs.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Society for Industrial and Applied Mathematics
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
CIRCULAR-ONES PROPERTY
dc.subject
CIRCULARY COMPATIBLE ONES
dc.subject
PROPER CIRCULAR-ARC BIOGRAPH
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs
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
2021-07-21T16:52:22Z
dc.identifier.eissn
1095-7146
dc.journal.volume
35
dc.journal.number
2
dc.journal.pagination
707-751
dc.journal.pais
Estados Unidos
dc.journal.ciudad
Philadelphia
dc.description.fil
Fil: Safe, Martin Dario. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Matemática Bahía Blanca. Universidad Nacional del Sur. Departamento de Matemática. Instituto de Matemática Bahía Blanca; Argentina
dc.journal.title
Siam Journal On Discrete Mathematics
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://epubs.siam.org/doi/10.1137/19M1266162
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://doi.org/10.1137/19M1266162
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/arxiv/https://arxiv.org/abs/1906.00321
Archivos asociados