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

DOI10.1016/J.TCS.2009.04.025MaRDI QIDQ837161zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)