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

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


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.6488 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.2361, with 3 seemingly having been the Holy Grail.
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
Publication size in sheets0.6
Book Ogihara Mitsunori, Tarui Jun (eds.): Theory and Applications of Models of Computation, Lecture Notes In Computer Science, vol. 6648, 2011, Springer, ISBN 978-3-642-20876-8
Keywords in EnglishConnected Graph; Exact Algorithm; Input Graph; Common Neighbor; Recursive Call
ASJC Classification1700 General Computer Science; 2614 Theoretical Computer Science
Languageen angielski
Score (nominal)13
Score sourcejournalList
ScoreMinisterial score = 20.0, 22-05-2019, ArticleFromJournal
Ministerial score (2013-2016) = 20.0, 22-05-2019, ArticleFromJournal
Publication indicators WoS Citations = 3; Scopus Citations = 4
Citation count*7 (2015-04-03)
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.
Are you sure?