3 papers
cs.DS2026
Online and Incremental Fractional Vertex Cover on Trees
Júlia Baligács, Bartłomiej Bosek, Yann Disser +5
In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori…
math.CO2024
Alon-Tarsi for hypergraphs
Marcin Anholcer, Bartłomiej Bosek, BartÅomiej Bosek +12
Given a hypergraph , define for every edge a linear expression with arguments corresponding to the vertices. Next, let the polynomial be the product of such…
cs.DM2024
First-Fit Coloring of Forests in Random Arrival Model
BartÅomiej Bosek, Grzegorz Gutowski, MichaÅ LasoÅ +1
We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm u…