Title of article
The Roberts characterization of proper and unit interval graphs
Author/Authors
Frederic Gardi، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2007
Pages
3
From page
2906
To page
2908
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 , Efficient representation , Characterizations , Constructive proof , Unit interval graphs
Journal title
Discrete Mathematics
Serial Year
2007
Journal title
Discrete Mathematics
Record number
947875
Link To Document