Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: equitable coloring

Sortuj według:

Ogranicz wyniki do:

Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines

Furmańczyk H., Kubale M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

2017

Vol. 65, nr 1

29--34

In the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s1 ≥ s2 ≥ s3 ≥ s4, respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Δ, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s1 = s2 = s3. If, however, Δ ≤ 4 and s1 ≥ 12s2, s2 = s3 = s4, then the problem can be solved to optimality in time O(n1.5). The same algorithm returns a solution of value at most 2 times optimal provided that s1 ≥ 2s2. Finally, we study the case s1 ≥ s2 ≥ s3 = s4 and give a 32/15-approximation algorithm running also in O(n1.5) time.

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

Furmańczyk H., Kubale M.

Archives of Control Sciences

2015

Vol. 25, no. 1

109--116

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.

Equitable coloring of graph products

Furmańczyk H.

Opuscula Mathematica

2006

Vol. 26, no. 1

31-44

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the "equitable chromatic number" of G and denoted by χ=(G). It is interesting to note that if a graph G is equitably k-colorable, it does not imply that it is equitably (k + 1)-colorable. The smallest integer k for which G is equitably k'-colorable for all k' ≥ k is called "the equitable chromatic threshold" of G and denoted by χ*=(G). In the paper we establish the equitable chromatic number and the equitable chromatic threshold for certain products of some highly-structured graphs. We extend the results from [2] for Cartesian, weak and strong tensor products.