Title of article :
A new representation of proper interval graphs with an application to clique-width
Author/Authors :
Heggernes، نويسنده , , Pinar and Meister، نويسنده , , Daniel and Papadopoulos، نويسنده , , Charis، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Abstract :
We introduce a new representation of proper interval graphs that can be computed in linear time and stored in O ( n ) space. This representation is a 2-dimensional vertex partition. It is particularly interesting with respect to clique-width. Based on this representation, we prove new upper bounds on the clique-width of proper interval graphs.
Keywords :
proper interval graphs , clique-width , Representation model
Journal title :
Electronic Notes in Discrete Mathematics
Journal title :
Electronic Notes in Discrete Mathematics
