Abstract | ||
---|---|---|
We characterize graphs that have intersection representations using unit intervals with open or closed ends such that all ends of the intervals are integral in terms of infinitely many minimal forbidden induced subgraphs. Furthermore, we provide a linear-time algorithm that decides if a given interval graph admits such an intersection representation. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.dam.2012.09.013 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
unit interval,interval graph,induced subgraphs,linear-time algorithm,integral mixed unit interval,closed end,intersection representation | Journal | 161 |
Issue | ISSN | Citations |
7-8 | 0166-218X | 4 |
PageRank | References | Authors |
0.56 | 13 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Van Bang Le | 1 | 481 | 66.67 |
Dieter Rautenbach | 2 | 946 | 138.87 |