The Roberts characterization of proper and unit interval graphs |
| |
| Authors: | Fré dé ric Gardi |
| |
| Affiliation: | Experian-Prologia, Parc Scientifique et Technologique de Luminy, case 919, bâtiment CCIMP, 13288 Marseille cedex 9, France |
| |
| Abstract: | In this note, a constructive proof that the classes of proper interval graphs and unit interval graphs coincide is given, a result originally established by Fred S. Roberts. Additionally, the proof yields a linear-time and space algorithm to compute a unit interval representation, given a proper interval graph as input. |
| |
| Keywords: | Proper interval graphs Unit interval graphs Constructive proof Efficient representation Characterizations |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
