Grundy antalet av en graf är det maximala antalet färger som används av den giriga färg algoritm över alla vertex beställningar. I detta papper studerar vi den beräkningsmässiga komplexiteten i Grundy Coloring, problemet med att avgöra om en viss graf har Grundy nummer minst k. Vi visar att Grundy Coloring kan lösas i tid O * (2 n ) på grafer i ordning n. Även om problemet är känd för att vara solvable i tid f (k, w) · n för grafer av trädbredd w, vi bevisar att under Exponential Time Hypothesis, det inte kan beräknas i tid O * (c w ), för någon konstant c. Vi överväger också två tidigare studerade varianter av Grundy Coloring, nämligen Svag Grundy Coloring och Ansluten Grundy Coloring. Vi visar att Svag Grundy Coloring är fastparameterdragbar med avseende på det svaga Grundy-numret. I skarp kontrast visar det sig att det redan är NP-komplett för k = 7 att kontrollera om en given graf har kopplat ihop Grundy-talet minst k.
REF visar en exakt algoritm för Grundy Number med O(2.443 n ).
Complexity of Grundy coloring and its variants
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}