114–117, 2000..
Planowanie zadań współdzielących zasoby W systemach wieloprocesorowych część zasobów nie może być wykorzystywana jednocześnie do wielu zadań. Problemem do rozwiązania jest tu optymalne zaplanowanie zadań dzielących zasoby. Muszą przy tym być spełnione warunki: zadania współdzielące zasoby nie mogą być wykonywane jednocześnie oraz każde żądanie wykonania dowolnego z zadań musi być prędzej czy później spełnione. Zakładając, że każde z zadań zostaje wykonane w jednej jednostce czasu, problem można przełożyć na problem multikolorowania grafu, którego wierzchołki reprezentują zadania do wykonania, a krawędzie między nimi oznaczają, że prace te dzielą pewien zasób i nie mogą być wykonywane w tym samym czasieAmotz Bar-Noy, Magnus M. Halldórsson, Guy Kortsarz, Ravit Salman, Hadas Shachnai, Sum multicoloring of graphs, „Journal of Algorithms” 37(2), s. 422–450, 1999..
Zobacz też kolorowanie grafu liczba chromatyczna liczba multichromatyczna multikolorowanie sumacyjne
Przypisy
Kategoria:Teoria grafów