Wyszukiwarka
Abstrakt
In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan
Cytowania
-
7
CrossRef
-
0
Web of Science
-
9
Scopus
Autorzy (2)
Cytuj jako
Pełna treść
pobierz publikację
pobrano 41 razy
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
Archives of Control Sciences
nr 25,
strony 109 - 116,
ISSN: 1230-2384 - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Furmańczyk H., Kubale M.: Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling// Archives of Control Sciences. -Vol. 25., iss. 1 (2015), s.109-116
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1515/acsc-2015-0007
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 156 razy