Linear-time recognition of Helly circular-arc models and graphs | ||
| dc.conicet.fuente | individual | |
| dc.conicet.organizacion | State University of Colorado - Fort Collins | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | State University of Colorado - Fort Collins | |
| dc.conicet.organizacion | Vanderbilt University | |
| dc.conicet.organizacion | Universidade Federal do Rio de Janeiro | |
| dc.conicet.paisOrganizacion | Estados Unidos | |
| dc.conicet.paisOrganizacion | Argentina | |
| dc.conicet.paisOrganizacion | Argentina | |
| dc.conicet.paisOrganizacion | Estados Unidos | |
| dc.conicet.paisOrganizacion | Estados Unidos | |
| dc.conicet.paisOrganizacion | Brasil | |
| dc.conicet.produccionid | 4452825 | |
| dc.contributor.author | Joeris, Benson L. | |
| dc.contributor.author | Lin, Min Chih | |
| dc.contributor.author | McConnell, Ross M. | |
| dc.contributor.author | Spinrad, Jeremy P. | |
| dc.contributor.author | Szwarcfiter, Jayme L. | |
| dc.date.accessioned | 2019-01-16T19:20:12Z | |
| dc.date.available | 2019-01-16T19:20:12Z | |
| dc.date.issued | 2011-02 | |
| dc.date.updated | 2019-01-14T17:59:50Z | |
| dc.description.abstract | A circular-arc model M is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then · is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n 3). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound. | es |
| dc.description.fil | Fil: Joeris, Benson L.. State University of Colorado - Fort Collins; Estados Unidos | |
| dc.description.fil | Fil: Lin, Min Chih. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; 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: Spinrad, Jeremy P.. Vanderbilt University; Estados Unidos | |
| dc.description.fil | Fil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L.; Linear-time recognition of Helly circular-arc models and graphs; Springer; Algorithmica; 59; 2; 2-2011; 215-239 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0178-4617 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/68150 | |
| dc.journal.number | 2 | es |
| dc.journal.pagination | 215-239 | es |
| dc.journal.pais | Alemania | es |
| dc.journal.title | Algorithmica | es |
| dc.journal.volume | 59 | es |
| dc.language.iso | eng | es |
| dc.publisher | Springer | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1007/s00453-009-9304-5 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://link.springer.com/article/10.1007%2Fs00453-009-9304-5 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | Algorithms | es |
| dc.subject | Circular-Arc Graphs | es |
| dc.subject | Forbidden Subgraphs | es |
| dc.subject | Helly Circular-Arc Graphs | es |
| dc.subject.classification | Matemática Pura | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Linear-time recognition of Helly circular-arc models and graphs | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.f1de6626-e247-427d-80ee-51cbe92ae99d_A.pdf
- Tamaño:
- 651.63 KB
- Formato:
- Adobe Portable Document Format