A Linear Time Algorithm for L(2,1)-Labeling of Trees

DOI10.1007/978-3-642-04128-0_4MaRDI QIDQ3639233zbMATH OpenOpenAlexFDO

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

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04128-0_4

zbMATH Keywords

graph labelinglinear time algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

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

Cited in

(23)

• \(L(2, 1)\)-labeling of circulant graphs
• \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
• The \(L(2,1)\)-labeling of unigraphs
• 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
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes
• Fast exact algorithm for L(2,1)-labeling of graphs
• The (p,q)-total labeling problem for trees
• Distance three labelings of trees
• L(2,1)-labeling of interval graphs
• L(3,1)-labeling of circulant graphs
• A note on \(L (2, 1)\)-labelling of trees
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• On (s,t)-relaxed L(2,1)-labeling of graphs
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks
• On \(n\)-fold \(L(j,k)\)-and circular \(L(j,k)\)-labelings of graphs
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• Injective colorings with arithmetic constraints
• On the complexity of labeled oriented trees

This page was built for publication: A Linear Time 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 Q3639233)