Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling - Publikacja - MOST Wiedzy

Wyszukiwarka

Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

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

  • 6

    CrossRef

  • 0

    Web of Science

  • 7

    Scopus

Autorzy (2)

Cytuj jako

Pełna treść

pobierz publikację
pobrano 17 razy
Wersja publikacji
Accepted albo Published Version
Licencja
Creative Commons: CC-BY-NC-ND 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 114 razy

Publikacje, które mogą cię zainteresować

Meta Tagi