L(2,1,1)-labeling is NP-complete for trees

Golovach, P. A.; Lidicky, B.; Paulusma, D.

doi:10.1007/978-3-642-13562-0_20

L(2,1,1)-labeling is NP-complete for trees

Golovach, P. A.; Lidicky, B.; Paulusma, D.

Authors

P. A. Golovach

B. Lidicky

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Contributors

Jan Kratochvíl
Editor

Angsheng Li
Editor

Jirí Fiala
Editor

Petr Kolman
Editor

Abstract

An L(p 1,p 2,p 3)-labeling of a graph G with span λ is a mapping f that assigns each vertex u of G an integer label 0 ≤ f(u) ≤ λ such that |f(u) − f(v)| ≥ p i whenever vertices u and v are of distance i for i ∈ {1,2,3}. We show that testing whether a given graph has an L(2,1,1)-labeling with some given span λ is NP-complete even for the class of trees.

Citation

Golovach, P. A., Lidicky, B., & Paulusma, D. (2010). L(2,1,1)-labeling is NP-complete for trees. In J. Kratochvíl, A. Li, J. Fiala, & P. Kolman (Eds.), Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings (211-221). https://doi.org/10.1007/978-3-642-13562-0_20

Conference Name	7th Annual Conference on Theory and Applications of Models of Computation
Conference Location	Prague, Czech Republic
Publication Date	Jan 1, 2010
Deposit Date	Oct 6, 2010
Publisher	Springer Verlag
Pages	211-221
Series Title	Lecture notes in computer science
Series Number	6108
Edition	7th
Book Title	Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings.
DOI	https://doi.org/10.1007/978-3-642-13562-0_20
Public URL	https://durham-repository.worktribe.com/output/1158568