Wydajny algorytm dla r-sprawiedliwego kolorowania grafów

Hanna Furmańczyk , Artur Koliński

Abstract

In the paper we consider the problem of r-equitable proper colouring of graphs in which the size of colour classes may differ by at most r. Such a graph colouring model has many applications. We present computational complexity results for some graph classes. We give also an example of a graph class that proper colouring is hard, an equitable colouring (r = 1) can be achieved in polynomial time, while an r-equitable colouring with r ≥­ 2 is again NP-hard. We formulate also very efficient algorithm for r-equitable colouring that has been tested on DIMACS graphs. Part of them are presented hereby.
Author Hanna Furmańczyk (FMPI / II)
Hanna Furmańczyk,,
- Institute of Informatics
, Artur Koliński (FMPI / II)
Artur Koliński,,
- Institute of Informatics
Other language title versionsEfficient algorithm for r-equitable graph coloring
Pages61-68
Publication size in sheets0.5
Book Świerniak Andrzej, Krystek Jolanta (eds.): Automatyzacja procesów dyskretnych: teoria i zastosowania, vol. 1, 2018, Politechnika Śląska, ISBN 978-83-7880-565-6, 245 p.
Keywords in Polishr-sprawiedliwe kolorowanie grafów, złożoność obliczeniowa, algorytm przybliżony
Keywords in Englishr-equitable graph coloring, computational complexity, approximate algorithm
Abstract in PolishW pracy rozważamy problem r-sprawiedliwego właściwego kolorowania grafów, w którym rozmiar klas kolorów może różnić się maksymalnie o wartość r. Taki model ma szerokie zastosowania praktyczne. Prezentujemy wyniki dotyczące złożoności problemu dla wybranych klas grafów. Podajemy przykład klasy grafów, dla której klasyczne kolorowanie jest trudne obliczeniowo, kolorowanie sprawiedliwe (r = 1) jest rozwiązywalne w czasie wielomianowym, podczas gdy kolorowanie r-sprawiedliwe z r ≥­­ 2 jest problemem NP-trudnym. Podajemy równie˙z bardzo wydajny algorytm dla r-sprawiedliwego kolorowania grafów, który został przetestowany na grafach pochodzących z biblioteki benchmarków DIMACS. Część wyników została zaprezentowana w niniejszej pracy.
Languagepl polski
LicenseRepository; published final; Other open licence; with publication
File
Furmanczyk_Hanna_Wydajny_algorytm_dla_r-sprawiedliwego_kolorowania_grafów_2018.pdf 209.38 KB
Score (nominal)20
Score sourcepublisherList
ScoreMinisterial score = 20.0, 26-02-2020, MonographChapterAuthor
Citation count*
Additional fields
UwagiKorzystanie z tego materiału jest możliwe zgodnie z właściwymi przepisami o dozwolonym użytku lub o innych wyjątkach przewidzianych w przepisach prawa, a korzystanie w szerszym zakresie wymaga uzyskania zgody uprawnionego.
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?