3 papers
cs.DS2021
Linear-time algorithm for vertex 2-coloring without monochromatic triangles on planar graphs
Michał Karpiński, Krzysztof Piecuch
In the problem of 2-coloring without monochromatic triangles (or triangle-tree 2-coloring), vertices of the simple, connected, undirected graph are colored with either 'black' or '…
cs.DS2020
An Optimal Algorithm for Online Multiple Knapsack
Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of bins (knapsacks) of equal…
cs.DS2017
On vertex coloring without monochromatic triangles
Michał Karpiński, Krzysztof Piecuch
We study a certain relaxation of the classic vertex coloring problem, namely, a coloring of vertices of undirected, simple graphs, such that there are no monochromatic triangles. W…