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
Pages
8
From page
27
To page
34
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
Serial Year
2009
Journal title
Electronic Notes in Discrete Mathematics
Record number
1454990
Link To Document