A Complete Characterisation of the Linear Clique-Width of Path Powers (Journal article)

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

A k-path power is the k-power graph of a simple path of arbitrary length. Path powers form a non-trivial subclass of proper interval graphs. Their clique-width is not bounded by a constant, and no polynomial-time algorithm is known for computing their clique-width or linear clique-width. We show that k-path powers above a certain size have linear clique-width exactly k?+?2, providing the first complete characterisation of the linear clique-width of a graph class of unbounded clique-width. Our characterisation results in a simple linear-time algorithm for computing the linear clique-width of all path powers.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
URI: https://olympias.lib.uoi.gr/jspui/handle/123456789/12695
Publisher: Springer-Verlag
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Files in This Item:
File Description SizeFormat 
Papadopoulos-2009-a complete characterisation.pdf226.03 kBAdobe PDFView/Open    Request a copy

 Please use this identifier to cite or link to this item:
  This item is a favorite for 0 people.

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