Wyszukiwarka
Abstrakt
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.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Tytuł wydania:
- Proceeedings of the 1st International Conference on Information Technology Gdańsk, 19-21 May 2008 strony 293 - 296
- Język:
- angielski
- Rok wydania:
- 2008
- Opis bibliograficzny:
- Bogdanowicz D., Giaro K.: Some results on trading model in a consensus list coloring// Proceeedings of the 1st International Conference on Information Technology Gdańsk, 19-21 May 2008/ ed. eds: A. Stepnowski [et al.]. Gdańsk: Gdańsk University of Technology, 2008, s.293-296
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 88 razy