5 papers
Dynamic domination and independence in sparse graphs
BartÅomiej Bosek, Wojciech Nadara, MichaÅ Pilipczuk +1
Let be a class of graphs of bounded expansion and be fixed. We give a dynamic data structure that for a given dynamic graph , updated by edge i…
Epistemic fair division of independence structures
Marcin Anholcer, Maciej Bartkowiak, BartÅomiej Bosek +1
We study the problem of fair division of indivisible goods with constraints imposed by a prescribed independence structure, that is, a family of subsets of goods closed under takin…
Dynamic data structures for twin-ordered matrices
BartÅomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…
Mrs. Correct and Majority Colorings
Marcin Anholcer, BartÅomiej Bosek, JarosÅaw Grytczuk +3
A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. In this note we simplify some proof techn…
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…