Mostrar el registro sencillo del ítem

Recognition and characterization of unit interval graphs with integer endpoints

Autordc.contributor.authorDurán, G. 
Autordc.contributor.authorFernández Slezak, F. 
Autordc.contributor.authorGrippo, L. N. 
Autordc.contributor.authorOliveira, F. de S. 
Autordc.contributor.authorSzwarcfiter, J. L. 
Fecha ingresodc.date.accessioned2018-11-26T19:42:14Z
Fecha disponibledc.date.available2018-11-26T19:42:14Z
Fecha de publicacióndc.date.issued2018-08-20
Cita de ítemdc.identifier.citationDiscrete Applied Mathematics Volumen: 245 Páginas: 168-176 Número especial: SIes_ES
Identificadordc.identifier.other10.1016/j.dam.2017.04.013
Identificadordc.identifier.urihttps://repositorio.uchile.cl/handle/2250/152907
Resumendc.description.abstractWe 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
Patrocinadordc.description.sponsorshipComplex 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 CAPESes_ES
Idiomadc.language.isoenes_ES
Publicadordc.publisherElsevieres_ES
Tipo de licenciadc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile*
Link a Licenciadc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/*
Fuentedc.sourceDiscrete Applied Mathematicses_ES
Palabras clavesdc.subjectUnit interval graphses_ES
Palabras clavesdc.subjectForbidden induced subgraphses_ES
Palabras clavesdc.subjectProper interval graphses_ES
Títulodc.titleRecognition and characterization of unit interval graphs with integer endpointses_ES
Tipo de documentodc.typeArtículo de revista
Catalogadoruchile.catalogadorrgfes_ES
Indizaciónuchile.indexArtículo de publicación ISIes_ES


Descargar archivo

Icon
Nombre:
Recognition-and-characterizati ...
Tamaño:
337.5Kb
Formato:
PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem

Attribution-NonCommercial-NoDerivs 3.0 Chile
Excepto si se señala otra cosa, la licencia del ítem se describe como Attribution-NonCommercial-NoDerivs 3.0 Chile