Recognition and characterization of unit interval graphs with integer endpoints

作者：Duran G; Fernandez Slezak F; Grippo L N; de S Oliveira F; Szwarcfiter J L

来源：Discrete Applied Mathematics, 2018, 245: 168-176.

DOI：10.1016/j.dam.2017.04.013

• Unit interval graphs
• Forbidden induced subgraphs
• Proper interval graphs

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.

• 出版日期2018-8-20