Rok 2024

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

  Publikacja

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

  - COMPUTERS & OPERATIONS RESEARCH - Rok 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...

  Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2016

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

  Publikacja

  • H. Furmańczyk
  • M. Kubale

  - ARS Mathematica Contemporanea - Rok 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...

  Pełny tekst do pobrania w portalu

Rok 2015

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

  Publikacja

  • H. Furmańczyk
  • M. Kubale

  - Archives of Control Sciences - Rok 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...

  Pełny tekst do pobrania w portalu