Fast exact algorithm for L(2,1)-labeling of graphs
Konstanty Junosza-Szaniawski , Jan Kratochvíl , Mathieu Liedloff , Peter Rossmanith , Paweł Rzążewski
AbstractAn L ( 2 , 1 ) -labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L ( 2 , 1 ) -span of a graph is the minimum possible span of its L ( 2 , 1 ) -labelings. We show how to compute the L ( 2 , 1 ) -span of a connected graph in time O ∗ ( 2.648 8 n ) . Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O ∗ ( 2.594 4 n ) for claw-free graphs, and in time O ∗ ( 2 n − r ( 2 + n r ) r ) for graphs having a dominating set of size r .
|Journal series||Theoretical Computer Science, ISSN 0304-3975|
|Publication size in sheets||0.6|
|Keywords in English||Exponential-time algorithm, graphs, L ( 2 , 1 ) -labeling|
|Score|| = 20.0, 01-02-2020, ArticleFromJournal|
= 20.0, 01-02-2020, ArticleFromJournal
|Publication indicators||= 6; = 6; : 2013 = 1.297; : 2013 = 0.516 (2) - 2013=0.652 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.