Fast exact algorithm for L(2,1)-labeling of graphs

Konstanty Junosza-Szaniawski , Jan Kratochvíl , Mathieu Liedloff , Peter Rossmanith , Paweł Rzążewski

Abstract

An 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 .
Author Konstanty Junosza-Szaniawski (FMIS / DAC)
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Jan Kratochvíl - [Charles University]
Jan Kratochvíl,,
-
-
, Mathieu Liedloff - [Universite d'Orleans]
Mathieu Liedloff,,
-
-
, Peter Rossmanith - [Rheinisch-Westfälische Technische Hochschule Aachen]
Peter Rossmanith,,
-
-
, Paweł Rzążewski (FMIS / DACSCM)
Paweł Rzążewski,,
- Department of Applied Computer Science and Computation Methods
Journal seriesTheoretical Computer Science, ISSN 0304-3975
Issue year2013
Vol505
No0
Pages42-54
Publication size in sheets0.6
Keywords in EnglishExponential-time algorithm, graphs, L ( 2 , 1 ) -labeling
ASJC Classification1700 General Computer Science; 2614 Theoretical Computer Science
DOIDOI:10.1016/j.tcs.2012.06.037
URL http://www.sciencedirect.com/science/article/pii/S0304397512006548
Languageen angielski
Score (nominal)20
Score sourcejournalList
ScoreMinisterial score = 20.0, 01-02-2020, ArticleFromJournal
Ministerial score (2013-2016) = 20.0, 01-02-2020, ArticleFromJournal
Publication indicators Scopus Citations = 6; WoS Citations = 6; Scopus SNIP (Source Normalised Impact per Paper): 2013 = 1.297; WoS Impact Factor: 2013 = 0.516 (2) - 2013=0.652 (5)
Citation count*
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?