Determining the \(L(2,1)\)-span in polynomial space
From MaRDI portal
Publication:2446848
DOI10.1016/j.dam.2013.03.027zbMath1286.05148arXiv1104.4506WikidataQ62595917 ScholiaQ62595917MaRDI QIDQ2446848
Jan Kratochvíl, Konstanty Junosza-Szaniawski, Mathieu Liedloff, Paweł Rzążewski
Publication date: 22 April 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1104.4506
exact algorithm; channel assignment problem; polynomial space; \(L(2, 1)\)-labeling; red-black graph
05C90: Applications of graph theory
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
94A40: Channel models (including quantum) in information and communication theory
Cites Work
- Unnamed Item
- Unnamed Item
- \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
- Exact algorithms for \(L(2,1)\)-labeling of graphs
- The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree
- An exact algorithm for the channel assignment problem
- On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs
- Channel assignment via fast zeta transform
- On the \(L(p,1)\)-labelling of graphs
- On Improved Exact Algorithms for L(2,1)-Labeling of Graphs
- Set Partitioning via Inclusion-Exclusion
- Labelling Graphs with a Condition at Distance 2
- Small Maximal Independent Sets and Faster Exact Graph Coloring
- Approximations for -Colorings of Graphs
- 3-coloring in time
- Determining the L(2,1)-Span in Polynomial Space
- Automata, Languages and Programming
- On cliques in graphs
- Fixed-parameter complexity of \(\lambda\)-labelings