Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871133 | Discrete Applied Mathematics | 2018 | 9 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
G. Durán, F. Fernández Slezak, L.N. Grippo, F.de S. Oliveira, J.L. Szwarcfiter,