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

DOI10.1007/978-3-642-13562-0_20zbMATH Open1284.05237OpenAlexW1588960957MaRDI QIDQ3569077FDOQ3569077

Authors: Petr A. Golovach, Bernard Lidický, Daniël Paulusma 

Publication date: 17 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13562-0_20

Recommendations

• Distance three labelings of trees
• Theoretical Computer Science
• Linear and cyclic distance-three labellings of trees
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cited In (10)

• Distance three labelings of trees
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• Title not available (Why is that?)
• Theoretical Computer Science
• Linear and cyclic distance-three labellings of trees
• The \(L(h,1,1)\)-labelling problem for trees
• Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees
• Automata, Languages and Programming
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Distance Constrained Labelings of Trees

This page was built for publication: \(L(2,1,1)\)-labeling is NP-complete for trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569077)