An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees

DOI10.1016/j.tcs.2009.04.025zbMath1172.68048OpenAlexW2140144078MaRDI QIDQ837161

Toshimasa Ishii, Toru Hasunuma, Yushi Uno, Hirotaka Ono

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.025

zbMATH Keywords

graph algorithmvertex coloring\(L(2, 1)\)-labelingfrequency/channel assignment

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A linear time algorithm for \(L(2,1)\)-labeling of trees ⋮ \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\) ⋮ Distance three labelings of trees ⋮ New upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs ⋮ On \((s,t)\)-relaxed \(L(2,1)\)-labeling of graphs ⋮ A sufficient condition for a tree to be \((\Delta+1)\)-\((2,1)\)-totally labelable

Cites Work

• \(T\)-colorings of graphs: recent results and open problems
• On \(L(d,1)\)-labelings of graphs
• \((p,1)\)-total labelling of graphs
• The \(L(2,1)\)-labelling of trees
• A survey on labeling graphs with a condition at distance two
• Labelling Graphs with a Condition at Distance 2
• Approximations for  -Colorings of Graphs
• On the $\lambda$-Number of $Q_n $ and Related Graphs
• The $L(2,1)$-Labeling Problem on Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Automata, Languages and Programming
• Fixed-parameter complexity of \(\lambda\)-labelings