Abstract | ||
---|---|---|
We study those unit interval graphs having a model with intervals of prescribed integer length. We present a structural result for this subclass which leads to a quadratic–time recognition algorithm of it, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.endm.2015.07.074 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
unit interval graphs,forbidden subgraphs,proper interval graphs | Integer,Discrete mathematics,Indifference graph,Combinatorics,Interval graph,Subclass,Chordal graph,Unit interval graphs,Induced subgraph,Mathematics,Certificate | Journal |
Volume | ISSN | Citations |
50 | 1571-0653 | 2 |
PageRank | References | Authors |
0.42 | 4 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Guillermo Durán | 1 | 296 | 29.28 |
Fernando Fernández | 2 | 2 | 0.76 |
Luciano N. Grippo | 3 | 28 | 7.79 |
Fabiano de S. Oliveira | 4 | 17 | 4.97 |
Jayme Luiz Szwarcfiter | 5 | 618 | 95.79 |