Computational complexity of distance edge labeling
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385824" target="_blank" >RIV/00216208:11320/18:10385824 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1016/j.dam.2017.01.007" target="_blank" >https://doi.org/10.1016/j.dam.2017.01.007</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.dam.2017.01.007" target="_blank" >10.1016/j.dam.2017.01.007</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Computational complexity of distance edge labeling
Popis výsledku v původním jazyce
The problem of DISTANCE EDGE LABELING is a variant of DISTANCE VERTEX LABELING (also known as L-2,L-1 labeling) that has been studied for more than twenty years and has many applications, such as frequency assignment. The DISTANCE EDGE LABELING problem asks whether the edges of a given graph can be labeled such that the labels of adjacent edges differ by at least two and the labels of edges at distance two differ by at least one. Labels are chosen from the set {0, 1,, lambda} for A fixed. We present a full classification of its computational complexity-a dichotomy between the polynomial-time solvable cases and the remaining cases which are NP-complete. We characterize graphs with lambda <= 4 which leads to a polynomial-time algorithm recognizing the class and we show NP-completeness for lambda >= 5 by several reductions from MONOTONE NOT ALL EQUAL 3-SAT. Moreover, there is an absolute constant c > 0 such that there is no 2(cn)-time algorithm deciding the DISTANCE EDGE LABELING problem unless the exponential time hypothesis fails.
Název v anglickém jazyce
Computational complexity of distance edge labeling
Popis výsledku anglicky
The problem of DISTANCE EDGE LABELING is a variant of DISTANCE VERTEX LABELING (also known as L-2,L-1 labeling) that has been studied for more than twenty years and has many applications, such as frequency assignment. The DISTANCE EDGE LABELING problem asks whether the edges of a given graph can be labeled such that the labels of adjacent edges differ by at least two and the labels of edges at distance two differ by at least one. Labels are chosen from the set {0, 1,, lambda} for A fixed. We present a full classification of its computational complexity-a dichotomy between the polynomial-time solvable cases and the remaining cases which are NP-complete. We characterize graphs with lambda <= 4 which leads to a polynomial-time algorithm recognizing the class and we show NP-completeness for lambda >= 5 by several reductions from MONOTONE NOT ALL EQUAL 3-SAT. Moreover, there is an absolute constant c > 0 such that there is no 2(cn)-time algorithm deciding the DISTANCE EDGE LABELING problem unless the exponential time hypothesis fails.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2018
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
Discrete Applied Mathematics
ISSN
0166-218X
e-ISSN
—
Svazek periodika
246
Číslo periodika v rámci svazku
9
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
19
Strana od-do
80-98
Kód UT WoS článku
000437996700008
EID výsledku v databázi Scopus
2-s2.0-85014108025