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

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

Toru Hasunuma, Hirotaka Ono, Toshimasa Ishii, Yushi Uno

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 algorithm; vertex coloring; \(L(2, 1)\)-labeling; frequency/channel assignment

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

Related Items

Distance three labelings of trees, New upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs, \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\), A linear time algorithm for \(L(2,1)\)-labeling of trees

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