On the proper intervalization of colored caterpillar trees

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

To access the full text documents, please follow this link: http://hdl.handle.net/2117/10751

dc.contributor	Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
dc.contributor	Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
dc.contributor.author	Álvarez Faura, M. del Carme
dc.contributor.author	Serna Iglesias, María José
dc.date	2009
dc.identifier.citation	Álvarez, M.; Serna, M. On the proper intervalization of colored caterpillar trees. "RAIRO. Theoretical informatics and applications", 2009, vol. 43, núm. 4, p. 667-686.
dc.identifier.citation	0988-3754
dc.identifier.citation	10.1051/ita/2009014
dc.identifier.uri	http://hdl.handle.net/2117/10751
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
dc.subject	Parallel algorithms
dc.subject	Computational complexity
dc.subject	Complexity
dc.subject	Caterpillar tree
dc.subject	Graph layout problems
dc.subject	Coloring
dc.subject	Algorismes paral·lels
dc.subject	Complexitat computacional
dc.title	On the proper intervalization of colored caterpillar trees
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/article
dc.description.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.

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author