On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs
From MaRDI portal
Publication:1944116
DOI10.1016/j.ipl.2011.04.010zbMath1260.05162WikidataQ62595924 ScholiaQ62595924MaRDI QIDQ1944116
Konstanty Junosza-Szaniawski, Paweł Rzążewski
Publication date: 4 April 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2011.04.010
combinatorial problems; analysis of algorithms; graph algorithms; exact algorithm; \(L(2,1)\)-labeling; list labeling; graph coloring model
68W40: Analysis of algorithms
05C15: Coloring of graphs and hypergraphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Fast exact algorithm for \(L(2,1)\)-labeling of graphs, Colorings with few colors: counting, enumeration and combinatorial bounds, Exact algorithm for graph homomorphism and locally injective graph homomorphism, Determining the \(L(2,1)\)-span in polynomial space
Cites Work
- \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
- Exact algorithms for \(L(2,1)\)-labeling of graphs
- On computing a longest path in a tree
- An exact algorithm for the channel assignment problem
- On Improved Exact Algorithms for L(2,1)-Labeling of Graphs
- Labelling Graphs with a Condition at Distance 2
- Theoretical Computer Science
- Fixed-parameter complexity of \(\lambda\)-labelings