A new representation of properinterval graphs with an application to clique-width (Journal article)

Papadopoulos, C./ Heggernes, P./ Meister, D.

We introduce anewrepresentation of properinterval 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 properinterval graphs.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Keywords: properinterval graphs, representation model, clique-width
URI: https://olympias.lib.uoi.gr/jspui/handle/123456789/12973
ISSN: 1571-0653
Publisher: Elsevier
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Files in This Item:
File Description SizeFormat 
Papadopoulos-2009-a new representation.pdf195.36 kBAdobe PDFView/Open    Request a copy


 Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12973
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.