Parameterized Complexity of Synchronization and Road Coloring

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10319646" target="_blank" >RIV/00216208:11320/15:10319646 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2685" target="_blank" >http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2685</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Complexity of Synchronization and Road Coloring

Popis výsledku v původním jazyce

First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unlessthe polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number ofstates, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.

Název v anglickém jazyce

Parameterized Complexity of Synchronization and Road Coloring

Popis výsledku anglicky

First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unlessthe polynomial hierarchy collapses. Second, we consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number ofstates, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

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 periodika

Discrete Mathematics and Theoretical Computer Science

ISSN

1462-7264

e-ISSN

—

Svazek periodika

17

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

23

Strana od-do

283-305

Kód UT WoS článku

000365862100002

EID výsledku v databázi Scopus

2-s2.0-84928378825