On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs

DOI10.1016/j.ipl.2011.04.010zbMath1260.05162OpenAlexW2080732177WikidataQ62595924 ScholiaQ62595924MaRDI QIDQ1944116

Konstanty Junosza-Szaniawski, Paweł Rzążewski

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.04.010

zbMATH Keywords

combinatorial problemsanalysis of algorithmsgraph algorithmsexact algorithm\(L(2,1)\)-labelinglist labelinggraph coloring model

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Fast exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ Determining the \(L(2,1)\)-span in polynomial space

Cites Work

• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• On computing a longest path in a tree
• An exact algorithm for the channel assignment problem
• On Improved Exact Algorithms for L(2,1)-Labeling of Graphs
• Labelling Graphs with a Condition at Distance 2
• Theoretical Computer Science
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs