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

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

Full metadata record
DC FieldValueLanguage
dc.contributor.authorPapadopoulos, C.en
dc.contributor.authorHeggernes, P.en
dc.contributor.authorMeister, D.en
dc.date.accessioned2015-11-24T17:23:05Z-
dc.date.available2015-11-24T17:23:05Z-
dc.identifier.urihttps://olympias.lib.uoi.gr/jspui/handle/123456789/12695-
dc.rightsDefault Licence-
dc.titleA Complete Characterisation of the Linear Clique-Width of Path Powersen
heal.typejournalArticle-
heal.type.enJournal articleen
heal.type.elΆρθρο Περιοδικούel
heal.identifier.primary10.1007/978-3-642-02017-9_27-
heal.languageen-
heal.accesscampus-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικώνel
heal.publicationDate2009-
heal.abstractA 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.en
heal.publisherSpringer-Verlagen
heal.journalNameTheory and Applications of Models of Computationen
heal.journalTypepeer reviewed-
heal.fullTextAvailabilityTRUE-
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:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12695
  This item is a favorite for 0 people.

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