On the complexity of distributed graph coloring with local minimality constraints - Publication - MOST Wiedzy

Search

On the complexity of distributed graph coloring with local minimality constraints

Abstract

Artykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.

Citations

  • 1 5

    CrossRef

  • 1 2

    Web of Science

  • 1 7

    Scopus

Details

Category:
Articles
Type:
artykuł w czasopiśmie wyróżnionym w JCR
Published in:
NETWORKS no. 54, pages 12 - 19,
ISSN: 0028-3045
Language:
English
Publication year:
2009
Bibliographic description:
Gavoille C., Klasing R., Kosowski A., Kuszner Ł., Navarra A.: On the complexity of distributed graph coloring with local minimality constraints// NETWORKS. -Vol. 54, nr. iss. 1 (2009), s.12-19
DOI:
Digital Object Identifier (open in new tab) 10.1002/net.20293
Verified by:
Gdańsk University of Technology

seen 14 times

Recommended for you

Meta Tags