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

DOI10.1007/978-3-642-13562-0_20MaRDI QIDQ3569077zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(10)

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

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)