L(2,1,1)-Labeling Is NP-Complete for Trees

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F10%3A10051725" target="_blank" >RIV/00216208:11320/10:10051725 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
L(2,1,1)-Labeling Is NP-Complete for Trees
Popis výsledku v původním jazyce
An L(p(1), p(2), p(3))-labeling of a graph G with span lambda is a mapping f that assigns each vertex u of G an integer label 0 {= f(u) {= lambda such that vertical bar f(u) - f(v)vertical bar }= p(i) whenever vertices u and v are of distance i for i isan element of {1, 2, 3}. We show that testing whether a given graph has an L(2, 1, 1)-labeling with some given span lambda is NP-complete even for the class of trees.
Název v anglickém jazyce
L(2,1,1)-Labeling Is NP-Complete for Trees
Popis výsledku anglicky
An L(p(1), p(2), p(3))-labeling of a graph G with span lambda is a mapping f that assigns each vertex u of G an integer label 0 {= f(u) {= lambda such that vertical bar f(u) - f(v)vertical bar }= p(i) whenever vertices u and v are of distance i for i isan element of {1, 2, 3}. We show that testing whether a given graph has an L(2, 1, 1)-labeling with some given span lambda is NP-complete even for the class of trees.

Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění
2010
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ů

Název statě ve sborníku
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS
ISBN
978-3-642-13561-3
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
11
Strana od-do
—
Název nakladatele
Springer-Verlag
Místo vydání
Berlin
Místo konání akce
Praha
Datum konání akce
7. 6. 2010
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000279560400019

Podobné výsledky(10)