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
topHow 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.
- 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.
- 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.
- 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).
- M.C. Golumbic, H. Kaplan and R. Shamir, On the complexity of DNA physical mapping. Adv. Appl. Math.15 (1994) 203–215.
- M.C. Golumbic, H. Kaplan and R. Shamir, Graph sandwich problems. J. Algorithms19 (1995) 449–473.
- M.C. Golumbic, Algorithmic graph theory and perfect graphs. Academic Press, New York (1980).
- M.C. Golumbic and R. Shamir, Complexity and algorithms for reasoning about time: A graph theoretical approach. J. ACM40 (1993) 1108–1113.
- D. Kuo and G.J. Chang, The profile minimization problem in trees. SIAM J. Comput.23 (1994) 71–81.
- H. Kaplan and R. Shamir, Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. SIAM J. Comput.25 (1996) 540–561.
- 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.
- B. Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebr. Discrete Methods7 (1986) 505–512.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.