An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs
DOI10.1016/j.dam.2023.07.012zbMath1526.05121OpenAlexW4386061827MaRDI QIDQ6069154
Publication date: 13 November 2023
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2023.07.012
graph algorithmapproximation algorithmunit disk graph\(L(2, 1)\)-labelingdistance-constrained labelingfrequency/channel assignment
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- \(L(2,1)\)-labeling of interval graphs
- On distance constrained labeling of disk graphs
- The \(L(2,1)\)-labeling of \(K_{1,n}\)-free graphs and its applications
- Unit disk graphs
- \(T\)-colorings of graphs: recent results and open problems
- Unit disk graph recognition is NP-hard
- \(L(h,1)\)-labeling subclasses of planar graphs
- A 116/13-approximation algorithm for \(L(2,1)\)-labeling of unit disk graphs
- \( L ( 2 , 1 )\)-labeling of disk intersection graphs
- A linear time algorithm for \(L(2,1)\)-labeling of trees
- On the \(L(p,1)\)-labelling of graphs
- A survey on labeling graphs with a condition at distance two
- Griggs and Yeh's Conjecture and $L(p,1)$-labelings
- Labelling Graphs with a Condition at Distance 2
- Approximations for -Colorings of Graphs
- Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
- The $L(2,1)$-Labeling Problem on Graphs
- Automata, Languages and Programming
This page was built for publication: An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs
