Search
Abstract
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.
Citations
-
2
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (4)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Monographic publication
- Type:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Title of issue:
- 21st International Symposium on Distributed Computing, Lemesos, Cyprus, 24-26 September 2007 strony 482 - 484
- Language:
- English
- Publication year:
- 2007
- Bibliographic description:
- Gavoille C., Klasing R., Kosowski A., Navarra A.: On the complexity of distributed greedy coloring// 21st International Symposium on Distributed Computing, Lemesos, Cyprus, 24-26 September 2007/ ed. ed. A. Pelc Berlin-Heidelberg: Springer-Verlag, 2007, s.482-484
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/978-3-540-75142-7_37
- Verified by:
- Gdańsk University of Technology
seen 67 times