Artykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie z listy filadelfijskiej
- Język
- angielski
- Rok wydania
- 2004
Źródło danych: MOSTWiedzy.pl - publikacja "Sum coloring of bipartite graphs with bounded degree." link otwiera się w nowej karcie
