RAIRO - Theoretical Informatics and Applications

Table of Contents - October 2009 - Volume 43, Issue 04  

Research Article

On the proper intervalization of colored caterpillar trees

Àlvarez, Carmea1 and Serna, Mariaa1

a1 ALBCOM Research Group, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, Campus Nord, Edifici Omega, C/ Jordi Girona Salgado 1-3, 08034 Barcelona, Spain; alvarez@lsi.upc.edu; mjserna@lsi.upc.edu

Abstract

This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For the hardness results we provide a reduction from the multiprocessor scheduling problem, while the polynomial time results follow from a characterization in terms of forbidden subgraphs.

(Received February 8 2007)

(Accepted May 14 2009)

(Online publication July 30 2009)

Key Words:

  • Complexity;
  • caterpillar tree;
  • graph layout problems;
  • coloring

Mathematics Subject Classification:

  • 68Q25;
  • 68W10