# On the proper intervalization of colored caterpillar trees

RAIRO - Theoretical Informatics and Applications (2009)

- Volume: 43, Issue: 4, page 667-686
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topÀlvarez, Carme, and Serna, Maria. "On the proper intervalization of colored caterpillar trees." RAIRO - Theoretical Informatics and Applications 43.4 (2009): 667-686. <http://eudml.org/doc/250603>.

@article{Àlvarez2009,

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.
},

author = {Àlvarez, Carme, Serna, Maria},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Complexity; caterpillar tree; graph layout problems; coloring; complexity},

language = {eng},

month = {7},

number = {4},

pages = {667-686},

publisher = {EDP Sciences},

title = {On the proper intervalization of colored caterpillar trees},

url = {http://eudml.org/doc/250603},

volume = {43},

year = {2009},

}

TY - JOUR

AU - Àlvarez, Carme

AU - Serna, Maria

TI - On the proper intervalization of colored caterpillar trees

JO - RAIRO - Theoretical Informatics and Applications

DA - 2009/7//

PB - EDP Sciences

VL - 43

IS - 4

SP - 667

EP - 686

AB -
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.

LA - eng

KW - Complexity; caterpillar tree; graph layout problems; coloring; complexity

UR - http://eudml.org/doc/250603

ER -

## References

top- C. Àlvarez, J. Díaz and M. Serna, The hardness of intervalizing four colored caterpillars. Discrete Math.235 (2001) 19–27. Zbl0977.05055
- C. Àlvarez, J. Díaz and M. Serna, Intervalizing colored graphs is NP-complete for caterpillars with hair length 2. Technical Report LSI 98-9-R, Universitat Politècnica de Catalunya (1998).
- H. Bodlaender, M.R. Fellows and M.T. Hallet, Beyond NP-completeness for problems of bounded width: hardness for the W-hierarchy, in 26th ACM Symposium on Theory of Computing (1994) 449–458. Zbl1345.68152
- J. Díaz, A.M. Gibbons, M.S. Paterson and J. Torán, The minsumcut problem, in Algorithms and Datastructure, edited by F. Dehen, R.J. Sack and N. Santoro. Lect. Notes Comput. Sci.519 (1991) 65–79. Zbl0764.68064
- M.J. Dinneen, VLSI Layouts and DNA physical mappings. Technical Report, Los Alamos National Laboratory (1996).
- M.R. Fellows, M.T. Hallet and W.T. Wareham, DNA physical mapping: Three ways difficult, in Algorithms-ESA'93, edited by T. Lengauer. Lect. Notes Comput. Sci.726 (1993) 157–168.
- P.W. Goldberg, M.C. Golumbic, H. Kaplan and R. Shamir, Four strikes against physical mapping of DNA. J. Comput. Biol.2 (1995) 139–152.
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979). Zbl0411.68039
- M.C. Golumbic, H. Kaplan and R. Shamir, On the complexity of DNA physical mapping. Adv. Appl. Math.15 (1994) 203–215. Zbl0806.92007
- M.C. Golumbic, H. Kaplan and R. Shamir, Graph sandwich problems. J. Algorithms19 (1995) 449–473. Zbl0838.68054
- M.C. Golumbic, Algorithmic graph theory and perfect graphs. Academic Press, New York (1980). Zbl0541.05054
- M.C. Golumbic and R. Shamir, Complexity and algorithms for reasoning about time: A graph theoretical approach. J. ACM40 (1993) 1108–1113. Zbl0795.68095
- D. Kuo and G.J. Chang, The profile minimization problem in trees. SIAM J. Comput.23 (1994) 71–81. Zbl0794.05117
- H. Kaplan and R. Shamir, Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. SIAM J. Comput.25 (1996) 540–561. Zbl0852.68072
- H. Kaplan, R. Shamir and R.E. Tarjan, Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput.28 (1999) 1906-1922. Zbl0928.68124
- B. Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebr. Discrete Methods7 (1986) 505–512. Zbl0624.68059

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.