Sum coloring of bipartite graphs with bounded degree.

Michał Małafiejski; Krzysztof Giaro; Robert Janczewski; Marek Kubale

Sum coloring of bipartite graphs with bounded degree.

Abstrakt

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 (4)

Michał Małafiejski dr hab. inż.
- Wydział Elektroniki, Telekomunikacji i Informatyki
- Politechnika Gdańska
Krzysztof Giaro prof. dr hab. inż.
- Wydział Elektroniki, Telekomunikacji i Informatyki
- Politechnika Gdańska
Robert Janczewski dr hab. inż.
- Wydział Elektroniki, Telekomunikacji i Informatyki
- Politechnika Gdańska
Marek Kubale prof. dr hab. inż.
- Wydział Elektroniki, Telekomunikacji i Informatyki
- Politechnika Gdańska

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie z listy filadelfijskiej
Język:: angielski
Rok wydania:: 2004
Opis bibliograficzny:: Małafiejski M., Giaro K., Janczewski R., Kubale M.: Sum coloring of bipartite graphs with bounded degree.// . -., (2004), s.0-0
Weryfikacja:: Politechnika Gdańska