Showing 2022Show all
2 papers · 1 filter
cs.DM2022
Approximation algorithms for job scheduling with block-type conflict graphs
Hanna Furmańczyk, Tytus Pikies, Inka Sokołowska +1
The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality crite…
cs.DM2022
Edge coloring of graphs of signed class 1 and 2
Robert Janczewski, Krzysztof Turowski, Bartłomiej Wróblewski
Recently, Behr introduced a notion of the chromatic index of signed graphs and proved that for every signed graph , it holds that \[ Δ(G)\leqχ'(G\text{, }σ)\leqΔ(G)+1\text…