INVESTIGADORES
DURAN Guillermo Alfredo
artículos
Título:
Recognition and characterization of unit interval graphs with integer endpoints
Autor/es:
DURÁN, G.; FERNÁNDEZ SLEZAK, F.; GRIPPO, L.N.; OLIVEIRA, F.DE S.; SZWARCFITER, J.L.
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2018 vol. 245 p. 168 - 176
ISSN:
0166-218X
Resumen:
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.
