On the complexity of exact algorithm for L (2, 1)-labeling of graphs

Konstanty Junosza-Szaniawski , Paweł Rzążewski

Abstract

L ( 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 ) .
Author Konstanty Junosza-Szaniawski (FMIS / DAC)
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Paweł Rzążewski (FMIS / DACSCM)
Paweł Rzążewski,,
- Department of Applied Computer Science and Computation Methods
Journal seriesInformation Processing Letters, ISSN 0020-0190, (A 20 pkt)
Issue year2011
Vol111
No14
Pages697-701
Keywords in EnglishAnalysis of algorithms, Combinatorial problems, Exact algorithm, Graph algorithms, Graph coloring model, L ( 2 , 1 ) -labeling
ASJC Classification1706 Computer Science Applications; 1710 Information Systems; 1711 Signal Processing; 2614 Theoretical Computer Science
DOIDOI:10.1016/j.ipl.2011.04.010
URL http://www.sciencedirect.com/science/article/pii/S0020019011001165
Score (nominal)20
Score sourcejournalList
Publication indicators Scopus Citations = 6; WoS Citations = 6; Scopus SNIP (Source Normalised Impact per Paper): 2011 = 0.898; WoS Impact Factor: 2011 = 0.455 (2) - 2011=0.547 (5)
Citation count*8 (2015-04-03)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?