Determining L(2,1)-Span in Polynomial Space

Konstanty Junosza-Szaniawski , Paweł Rzążewski


A \$k\$-L(2,1)-labeling of a graph is a function from its vertex set into the set \$\\textbackslash\\0,...,k\\textbackslash\\\$, such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. It is known that finding the smallest \$k\$ admitting the existence of a \$k\$-L(2,1)-labeling of any given graph is NP-Complete. In this paper we present an algorithm for this problem, which works in time \$O(\\textbackslash\complexity \\textasciicircum\n)\$ and polynomial memory, where \$\\textbackslash\eps\$ is an arbitrarily small positive constant. This is the first exact algorithm for L(2,1)-labeling problem with time complexity \$O(c\\textasciicircum\n)\$ for some constant \$c\$ and polynomial space complexity.
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
Publication size in sheets0.55
Book Heggernes Pinar (eds.): GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2016, vol. 9941, 2016, SPRINGER INT PUBLISHING AG, ISBN 978-3-662-53536-3, [978-3-662-53535-6]
Keywords in English68R10, 05C15, 05C85, Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics, G.2.2, Mathematics - Combinatorics
Languageen angielski
Score (nominal)15
ScoreMinisterial score = 15.0, 05-09-2019, BookChapterMatConfByConferenceseries
Ministerial score (2013-2016) = 15.0, 05-09-2019, BookChapterMatConfByConferenceseries
Citation count*
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?