Fast Exact Algorithm for L(2, 1)-Labeling of Graphs
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10108191" target="_blank" >RIV/00216208:11320/11:10108191 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-20877-5_9" target="_blank" >http://dx.doi.org/10.1007/978-3-642-20877-5_9</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-20877-5_9" target="_blank" >10.1007/978-3-642-20877-5_9</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Fast Exact Algorithm for L(2, 1)-Labeling of Graphs
Popis výsledku v původním jazyce
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 isthe 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.
Název v anglickém jazyce
Fast Exact Algorithm for L(2, 1)-Labeling of Graphs
Popis výsledku anglicky
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 isthe 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.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Lecture Notes in Computer Science
ISSN
0302-9743
e-ISSN
—
Svazek periodika
6648
Číslo periodika v rámci svazku
6648
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
12
Strana od-do
82-93
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—