1 January 2018 in Discrete Applied Mathematics
1 September 2016 in Archives of Control Sciences
In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs
1 February 2017 in Bulletin Of The Polish Academy Of Sciences-Technical Sciences
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.
5 February 2016 in Ars Mathematica Contemporanea
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 it is denoted by χ = (G). In this paper the problem of determinig χ = for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas of cubic graphs is solvable in polynomial time, the problem of equitable coloring becomes NP-hard for these graphs. We provide polynomially solvable cases of coronas of cubic graphs and prove the NP-hardness in a general case. As a by-product we obtain a simple linear time algorithm for equitable coloring of such graphs which uses χ = (G) or χ = (G) + 1 colors. Our algorithm is best possible, unless P=NP. Consequently, cubical coronas seem to be the only known class of graphs for which equitable coloring is harder than ordinary coloring.
1 March 2015 in Archives of Control Sciences
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
16 May 2008 in Information Processing Letters