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

DOI10.1016/J.TCS.2009.04.025zbMATH Open1172.68048OpenAlexW2140144078MaRDI QIDQ837161FDOQ837161

Authors: Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, 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

Recommendations

• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• A linear time algorithm for \(L(2,1)\)-labeling of trees
• The $L(2,1)$-Labeling Problem on Graphs
• The \(L(2,1)\)-labelling of trees

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (20)

• Distance three labelings of trees
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• New upper bounds on the \(L(2,1)\)-labeling of the skew and converse skew product graphs
• Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks
• On the complexity of labeled oriented trees
• A sufficient condition for a tree to be \((\Delta+1)\)-\((2,1)\)-totally labelable
• A linear time algorithm for \(L(2,1)\)-labeling of trees
• On \((s,t)\)-relaxed \(L(2,1)\)-labeling of graphs
• \(L(2,1,1)\)-labeling is NP-complete for trees
• Algorithmic aspects of the \(S\)-labeling problem
• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• \(L(h,1,1)\)-labeling of outerplanar graphs
• The \(L(h,1,1)\)-labelling problem for trees
• Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees
• A complete \(L (2, 1)\) span characterization for small trees
• \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms
• A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata
• L(h,1,1)-Labeling of Outerplanar Graphs
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• The \(L(2,1)\)-labeling of unigraphs

This page was built for publication: An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees

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