Notes on complexity of packing coloring
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10385822" target="_blank" >RIV/00216208:11320/18:10385822 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1016/j.ipl.2018.04.012" target="_blank" >https://doi.org/10.1016/j.ipl.2018.04.012</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ipl.2018.04.012" target="_blank" >10.1016/j.ipl.2018.04.012</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Notes on complexity of packing coloring
Popis výsledku v původním jazyce
A packing k-coloring for some integer k of a graph G = (V, E) is a mapping phi : V -> {1, . . . , k} such that any two vertices u, v of color phi(u) = phi(v) are in distance at least phi(u) + 1. This concept is motivated by frequency assignment problems. The packing chromatic number of G is the smallest k such that there exists a packing k-coloring of G. Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n(1/)(2-epsilon) for any epsilon > 0. In addition, we design an FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
Název v anglickém jazyce
Notes on complexity of packing coloring
Popis výsledku anglicky
A packing k-coloring for some integer k of a graph G = (V, E) is a mapping phi : V -> {1, . . . , k} such that any two vertices u, v of color phi(u) = phi(v) are in distance at least phi(u) + 1. This concept is motivated by frequency assignment problems. The packing chromatic number of G is the smallest k such that there exists a packing k-coloring of G. Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n(1/)(2-epsilon) for any epsilon > 0. In addition, we design an FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
Klasifikace
Druh
J<sub>imp</sub> - Č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)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA17-09142S" target="_blank" >GA17-09142S: Moderní algoritmy: Nové výzvy komplexních dat</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
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ů
Údaje specifické pro druh výsledku
Název periodika
Information Processing Letters
ISSN
0020-0190
e-ISSN
—
Svazek periodika
137
Číslo periodika v rámci svazku
9
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
5
Strana od-do
6-10
Kód UT WoS článku
000438480600002
EID výsledku v databázi Scopus
2-s2.0-85046782814