On the complexity of rainbow coloring problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00106820" target="_blank" >RIV/00216224:14330/18:00106820 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

On the complexity of rainbow coloring problems

Popis výsledku v původním jazyce

An edge-colored graph is said to be rainbow connected if between each pair of vertices there exists a path which uses each color at most once. The rainbow connection number, denoted by , is the minimum number of colors needed to make rainbow connected. Along with its variants, which consider vertex colorings and/or so-called strong colorings, the rainbow connection number has been studied from both the algorithmic and graph-theoretic points of view. In this paper we present a range of new results on the computational complexity of computing the four major variants of the rainbow connection number. In particular, we prove that the Strong Rainbow Vertex Coloring problem is -complete even on graphs of diameter , and also when the number of colors is restricted to . On the other hand, we show that if the number of colors is fixed then all of the considered problems can be solved in linear time on graphs of bounded treewidth. Moreover, we provide a linear-time algorithm which decides whether it is possible to obtain a rainbow coloring by saving a fixed number of colors from a trivial upper bound. Finally, we give a linear-time algorithm for computing the exact rainbow connection numbers for three variants of the problem on graphs of bounded vertex cover number.

Název v anglickém jazyce

On the complexity of rainbow coloring problems

Popis výsledku anglicky

An edge-colored graph is said to be rainbow connected if between each pair of vertices there exists a path which uses each color at most once. The rainbow connection number, denoted by , is the minimum number of colors needed to make rainbow connected. Along with its variants, which consider vertex colorings and/or so-called strong colorings, the rainbow connection number has been studied from both the algorithmic and graph-theoretic points of view. In this paper we present a range of new results on the computational complexity of computing the four major variants of the rainbow connection number. In particular, we prove that the Strong Rainbow Vertex Coloring problem is -complete even on graphs of diameter , and also when the number of colors is restricted to . On the other hand, we show that if the number of colors is fixed then all of the considered problems can be solved in linear time on graphs of bounded treewidth. Moreover, we provide a linear-time algorithm which decides whether it is possible to obtain a rainbow coloring by saving a fixed number of colors from a trivial upper bound. Finally, we give a linear-time algorithm for computing the exact rainbow connection numbers for three variants of the problem on graphs of bounded vertex cover number.

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

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

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ů

Název periodika

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

246

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

38-48

Kód UT WoS článku

000437996700005

EID výsledku v databázi Scopus

2-s2.0-85006790245