Repozytorium publikacji - Politechnika Gdańska

Konsensusowy model kolorowania grafów - uogólnienie kolorowania listowego, został zdefiniowany przez Mahadeva i Robertsa w 2002 jako użyteczne narzędzie teoretyczne w niektórych zagadnieniach bioinformatycznych. Pozostaje on jednak słabo rozpoznany pod względem własności algorytmicznych. Wykazujemy, że problem kolorowania grafów pełnych w tym modelu jest wielomianowy, co można uogólnić na częściowe k-drzewa przy ustalonym ograniczeniu górnym na k oraz łączną liczbę używanych barw. Jednak pominięcie tych ograniczeń proawdzi do NP-trudności nawet dla grafów będących prostymi drzewami.

Autorzy

• Damian Bogdanowicz link otwiera się w nowej karcie ,
• prof. dr hab. inż. Krzysztof Giaro link otwiera się w nowej karcie