An \mbox{O}(n^{1.75}) Algorithm for L(2,1)-Labeling of Trees

DOI10.1007/978-3-540-69903-3_18MaRDI QIDQ3512458zbMATH OpenOpenAlexFDO

Authors Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno

Publication date 15 July 2008

Published in Algorithm Theory – SWAT 2008 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69903-3_18

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Recommendations

• An 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

• \(T\)-colorings of graphs: recent results and open problems
• 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
• The $L(2,1)$-Labeling Problem on Graphs
• The L(2,1)-labelling of trees

Cited in

(13)

• Characterization results for the \(L(2, 1, 1)\)-labeling problem on trees
• A linear time algorithm for L(2,1)-labeling of trees
• A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• The $L(2,1)$-Labeling Problem on Graphs
• A note on \(L (2, 1)\)-labelling of trees
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• \([1,2]\)-sets and \([1,2]\)-total sets in trees with algorithms
• On the complexity of labeled oriented trees
• (2,1)-total labelling of trees with sparse vertices of maximum degree
• The \(L(h,1,1)\)-labelling problem for trees

This page was built for publication: An $\mbox{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 Q3512458)