A linear time algorithm for \(L(2,1)\)-labeling of trees
From MaRDI portal
Publication:2375957
DOI10.1007/s00453-012-9657-zzbMath1292.05246OpenAlexW2563363393MaRDI QIDQ2375957
Yushi Uno, Hirotaka Ono, Toru Hasunuma, Toshimasa Ishii
Publication date: 25 June 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9657-z
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
Computing L(p,1)-Labeling with Combined Parameters ⋮ On radio connection number of graphs ⋮ An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs ⋮ Graph covers: where topology meets computer science, and simple means difficult ⋮ A complete \(L (2, 1)\) span characterization for small trees ⋮ Computing \(L(p, 1)\)-labeling with combined parameters ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph
Cites Work
- An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
- On \(L(d,1)\)-labelings of graphs
- The \(L(2,1)\)-labelling of trees
- A survey on labeling graphs with a condition at distance two
- Griggs and Yeh's Conjecture and $L(p,1)$-labelings
- Beyond the flow decomposition barrier
- Distance Constrained Labelings of Trees
- Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
- Exact Algorithms for L(2,1)-Labeling of Graphs
- A Linear Time Algorithm for L(2,1)-Labeling of Trees
- Labelling Graphs with a Condition at Distance 2
- Approximations for -Colorings of 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
This page was built for publication: A linear time algorithm for \(L(2,1)\)-labeling of trees
