W pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
Autorzy
- Cyril Gavoille,
- Ralf Klasing,
- dr inż. Adrian Kosowski link otwiera się w nowej karcie ,
- Alfredo Navarra
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1007/978-3-540-75142-7_37
- Kategoria
- Publikacja monograficzna
- Typ
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Język
- angielski
- Rok wydania
- 2007
Źródło danych: MOSTWiedzy.pl - publikacja "On the complexity of distributed greedy coloring" link otwiera się w nowej karcie
