Year 2024

• Approximation algorithms for job scheduling with block-type conflict graphs

  Publication

  • H. Furmańczyk
  • T. Pikies
  • I. Sokołowska
  • K. Turowski

  - COMPUTERS & OPERATIONS RESEARCH - Year 2024

  The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...

  Full text to download in external service

Year 2016

• Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring

  Publication

  • H. Furmańczyk
  • M. Kubale

  - ARS Mathematica Contemporanea - Year 2016

  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. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...

  Full text available to download

Year 2015

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

  Publication

  • H. Furmańczyk
  • M. Kubale

  - Archives of Control Sciences - Year 2015

  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...

  Full text available to download