Complexity of Road Coloring with Prescribed Reset Words

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10392117" target="_blank" >RIV/00216208:11320/19:10392117 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=xZldR8Di5w" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=xZldR8Di5w</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jcss.2016.05.009" target="_blank" >10.1016/j.jcss.2016.05.009</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity of Road Coloring with Prescribed Reset Words

Popis výsledku v původním jazyce

By the Road Coloring Theorem (Trahtman, 2008), the edges of any given aperiodic strongly connected directed multigraph with a constant out-degree can be colored such that the resulting automaton admits a reset word. There may also be a need for a particular reset word to be admitted. In this paper we consider the following problem: given a word w and digraph G, is it true that G has a coloring that is synchronized by w? We show that it is NP-complete for certain fixed words. For the binary alphabet we present a classification that separates such words from those that make the problem solvable in polynomial time. The classification differs if we consider only strongly connected multigraphs. In this restricted setting the classification remains incomplete.

Název v anglickém jazyce

Complexity of Road Coloring with Prescribed Reset Words

Popis výsledku anglicky

By the Road Coloring Theorem (Trahtman, 2008), the edges of any given aperiodic strongly connected directed multigraph with a constant out-degree can be colored such that the resulting automaton admits a reset word. There may also be a need for a particular reset word to be admitted. In this paper we consider the following problem: given a word w and digraph G, is it true that G has a coloring that is synchronized by w? We show that it is NP-complete for certain fixed words. For the binary alphabet we present a classification that separates such words from those that make the problem solvable in polynomial time. The classification differs if we consider only strongly connected multigraphs. In this restricted setting the classification remains incomplete.

Druh

J_imp - Č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)

Projekt

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

Návaznosti

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

Rok uplatnění

2019

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

Journal of Computer and System Sciences

ISSN

0022-0000

e-ISSN

—

Svazek periodika

Neuveden

Číslo periodika v rámci svazku

červenec

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

24

Strana od-do

763-786

Kód UT WoS článku

000472246300020

EID výsledku v databázi Scopus

2-s2.0-85048737408