Recognition and characterization of unit interval graphs with integer endpoints
| Author | dc.contributor.author | Durán, G. | |
| Author | dc.contributor.author | Fernández Slezak, F. | |
| Author | dc.contributor.author | Grippo, L. N. | |
| Author | dc.contributor.author | Oliveira, F. de S. | |
| Author | dc.contributor.author | Szwarcfiter, J. L. | |
| Admission date | dc.date.accessioned | 2018-11-26T19:42:14Z | |
| Available date | dc.date.available | 2018-11-26T19:42:14Z | |
| Publication date | dc.date.issued | 2018-08-20 | |
| Cita de ítem | dc.identifier.citation | Discrete Applied Mathematics Volumen: 245 Páginas: 168-176 Número especial: SI | es_ES |
| Identifier | dc.identifier.other | 10.1016/j.dam.2017.04.013 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/152907 | |
| Abstract | dc.description.abstract | We study those unit interval graphs having a model with intervals of integer endpoints and prescribed length. We present a structural result for this graph subclass which leads to a quadratic-time recognition algorithm, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. We also present a quadratic-time algorithm to build, given a unit interval graph, a unit interval model with integer endpoints for which the interval length is as minimum as possible. (C) 2017 Elsevier B.V. All rights reserved. | es_ES |
| Patrocinador | dc.description.sponsorship | Complex Engineering Systems Institute, Chile CONICYT - PIA - FB0816; ICM P-05-004-F ANPCyT PICT-2012-1324 UBACyT (Argentina) 20020130100808BA PIO CONICET UNGS-144-20140100011-CO FAPERJ CNPq CAPES | es_ES |
| Lenguage | dc.language.iso | en | es_ES |
| Publisher | dc.publisher | Elsevier | es_ES |
| Type of license | dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | * |
| Link to License | dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | * |
| Source | dc.source | Discrete Applied Mathematics | es_ES |
| Keywords | dc.subject | Unit interval graphs | es_ES |
| Keywords | dc.subject | Forbidden induced subgraphs | es_ES |
| Keywords | dc.subject | Proper interval graphs | es_ES |
| Título | dc.title | Recognition and characterization of unit interval graphs with integer endpoints | es_ES |
| Document type | dc.type | Artículo de revista | |
| Cataloguer | uchile.catalogador | rgf | es_ES |
| Indexation | uchile.index | Artículo de publicación ISI | es_ES |
Files in this item
This item appears in the following Collection(s)
-
Artículos de revistas
Artículos de revistas
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile