On the complexity of exact algorithm for L (2, 1)-labeling of graphs
Konstanty Junosza-Szaniawski , Paweł Rzążewski
AbstractL ( 2 , 1 ) -labeling is a graph coloring model inspired by a frequency assignment in telecommunication. It asks for such a labeling of vertices with nonnegative integers that adjacent vertices get labels that differ by at least 2 and vertices in distance 2 get different labels. It is known that for any k ⩾ 4 it is NP-complete to determine if a graph has a L ( 2 , 1 ) -labeling with no label greater than k. In this paper we present a new bound on complexity of an algorithm for finding an optimal L ( 2 , 1 ) -labeling (i.e. an L ( 2 , 1 ) -labeling in which the largest label is the least possible). We improve the upper complexity bound of the algorithm from O ⁎ ( 3.5616 n ) to O ⁎ ( 3.2361 n ) . Moreover, we establish a lower complexity bound of the presented algorithm, which is Ω ⁎ ( 3.0739 n ) .
|Journal series||Information Processing Letters, ISSN 0020-0190, (A 20 pkt)|
|Keywords in English||Analysis of algorithms, Combinatorial problems, Exact algorithm, Graph algorithms, Graph coloring model, L ( 2 , 1 ) -labeling|
|ASJC Classification||; ; ;|
|Publication indicators||= 6; = 6; : 2011 = 0.898; : 2011 = 0.455 (2) - 2011=0.547 (5)|
|Citation count*||8 (2015-04-03)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.