Mostrar el registro sencillo del ítem

dc.contributor.author
Duran, Guillermo Alfredo  
dc.contributor.author
Fernández Slezak, F.  
dc.contributor.author
Grippo, L.N.  
dc.contributor.author
Oliveira, F.de S.  
dc.contributor.author
Szwarcfiter, Jayme L.  
dc.date.available
2018-06-27T21:14:59Z  
dc.date.issued
2017-06  
dc.identifier.citation
Duran, Guillermo Alfredo; Fernández Slezak, F.; Grippo, L.N.; Oliveira, F.de S.; Szwarcfiter, Jayme L.; Recognition and characterization of unit interval graphs with integer endpoints; Elsevier Science; Discrete Applied Mathematics; 245; 6-2017; 168-176  
dc.identifier.issn
0166-218X  
dc.identifier.uri
http://hdl.handle.net/11336/50305  
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.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Elsevier Science  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
Forbidden Induced Subgraphs  
dc.subject
Proper Interval Graphs  
dc.subject
Unit Interval Graphs  
dc.subject.classification
Matemática Pura  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Recognition and characterization of unit interval graphs with integer endpoints  
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
2018-06-26T13:54:33Z  
dc.journal.volume
245  
dc.journal.pagination
168-176  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
dc.description.fil
Fil: Duran, Guillermo Alfredo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Chile; Chile. Universidad de Buenos Aires; Argentina  
dc.description.fil
Fil: Fernández Slezak, F.. Universidad de Buenos Aires; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina  
dc.description.fil
Fil: Grippo, L.N.. Universidad Nacional de General Sarmiento; Argentina  
dc.description.fil
Fil: Oliveira, F.de S.. Universidade do Estado de Rio do Janeiro; Brasil  
dc.description.fil
Fil: Szwarcfiter, Jayme L.. Universidade do Estado de Rio do Janeiro; Brasil. Universidade Federal do Rio de Janeiro; Brasil  
dc.journal.title
Discrete Applied Mathematics  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2017.04.013  

Archivos asociados
Thumbnail
 
Tamaño: 392.5Kb
Formato: PDF
.