A new representation of properinterval graphs with an application to clique-width
Loading...
Date
Authors
Papadopoulos, C.
Heggernes, P.
Meister, D.
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
Type
Type of the conference item
Journal type
peer reviewed
Educational material type
Conference Name
Journal name
Electronic Notes in Discrete Mathematics
Book name
Book series
Book edition
Alternative title / Subtitle
Description
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.
Description
Keywords
properinterval graphs, representation model, clique-width
Subject classification
Citation
Link
Language
en
Publishing department/division
Advisor name
Examining committee
General Description / Additional Comments
Institution and School/Department of submitter
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών