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.
Authors
- Cyril Gavoille,
- Ralf Klasing,
- dr inż. Adrian Kosowski link open in new tab ,
- Alfredo Navarra
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1007/978-3-540-75142-7_37
- Category
- Publikacja monograficzna
- Type
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Language
- angielski
- Publication year
- 2007
Source: MOSTWiedzy.pl - publication "On the complexity of distributed greedy coloring" link open in new tab
