Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems - (Extended Abstract)

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-42634-1_6" target="_blank" >http://dx.doi.org/10.1007/978-3-319-42634-1_6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-42634-1_6" target="_blank" >10.1007/978-3-319-42634-1_6</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems - (Extended Abstract)

Popis výsledku v původním jazyce

We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique width. We rephrase the distance constrained graph labeling problem as a specific uniform variant of the Channel Assignment problem and show that this problem is fixed parameter tractable when parameterized by the neighborhood diversity together with the largest weight. Consequently, every L(p1,p2,...,pk)-labeling problem is FPT when parameterized by the neighborhood diversity, the maximum p_i and k . Finally, we show that the uniform variant of the Channel Assignment problem becomes NP-complete when generalized to graphs of bounded clique width.

Název v anglickém jazyce

Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems - (Extended Abstract)

Popis výsledku anglicky

We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique width. We rephrase the distance constrained graph labeling problem as a specific uniform variant of the Channel Assignment problem and show that this problem is fixed parameter tractable when parameterized by the neighborhood diversity together with the largest weight. Consequently, every L(p1,p2,...,pk)-labeling problem is FPT when parameterized by the neighborhood diversity, the maximum p_i and k . Finally, we show that the uniform variant of the Channel Assignment problem becomes NP-complete when generalized to graphs of bounded clique width.

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

COMPUTING AND COMBINATORICS, COCOON 2016

ISBN

978-3-319-42633-4

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

67-78

Název nakladatele

Springer Verlag

Místo vydání

Hi Chi Minh City

Místo konání akce

Ho Chi Minh City

Datum konání akce

2. 8. 2016

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

WRD - Celosvětová akce

Kód UT WoS článku

000389726400006