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

Wyszukiwarka

On the complexity of distributed graph coloring with local minimality constraints

Abstrakt

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.

Cytowania

  • 1 5

    CrossRef

  • 1 4

    Web of Science

  • 2 0

    Scopus

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 wyróżnionym w JCR
Opublikowano w:
NETWORKS nr 54, strony 12 - 19,
ISSN: 0028-3045
Język:
angielski
Rok wydania:
2009
Opis bibliograficzny:
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:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1002/net.20293
Weryfikacja:
Politechnika Gdańska

wyświetlono 15 razy

Publikacje, które mogą cię zainteresować

Meta Tagi