Computational complexity of distance edge labeling

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10312383" target="_blank" >RIV/00216208:11320/16:10312383 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-29516-9_24" target="_blank" >http://dx.doi.org/10.1007/978-3-319-29516-9_24</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-29516-9_24" target="_blank" >10.1007/978-3-319-29516-9_24</a>

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 L2,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, . . . , λ} for λ fixed. We present a full classification of its computational complexity-a dichotomy between the polynomially solvable cases and the remaining cases which are NP-complete. We characterize graphs with λ LESS-THAN OR EQUAL TO 4 which leads to a polynomial-time algorithm recognizing the class and we show NP-completeness for λ GREATER-THAN OR EQUAL TO 5 by several reductions from Monotone Not All Equal 3-SAT.

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 L2,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, . . . , λ} for λ fixed. We present a full classification of its computational complexity-a dichotomy between the polynomially solvable cases and the remaining cases which are NP-complete. We characterize graphs with λ LESS-THAN OR EQUAL TO 4 which leads to a polynomial-time algorithm recognizing the class and we show NP-completeness for λ GREATER-THAN OR EQUAL TO 5 by several reductions from Monotone Not All Equal 3-SAT.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

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

Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers

ISBN

978-3-319-29515-2

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

287-298

Název nakladatele

Springer

Místo vydání

Springer Verlag (Germany)

Místo konání akce

Verona, Itálie

Datum konání akce

5. 10. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—