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

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

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, December). L(2,1,1)-labeling is NP-complete for trees. Presented at 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 7th Annual Conference on Theory and Applications of Models of Computation
• Publication Date: Jan 1, 2010
• Deposit Date: Oct 6, 2010
• Print ISSN: 0302-9743
• 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