Determining the \(L(2,1)\)-span in polynomial space

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

zbMATH Keywords

exact algorithm; channel assignment problem; polynomial space; \(L(2, 1)\)-labeling; red-black graph

Mathematics Subject Classification ID

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