12 citations · 12 across the 3 of their papers we have counts for
5 papers
A lazy approach to on-line bipartite matching
Jakub Kozik, Grzegorz Matecki
We present a new approach, called a lazy matching, to the problem of on-line matching on bipartite graphs. Imagine that one side of a graph is given and the vertices of the other s…
An easy subexponential bound for online chain partitioning
Bartłomiej Bosek, Hal A. Kierstead, Tomasz Krawczyk +2
Bosek and Krawczyk exhibited an online algorithm for partitioning an online poset of width into chains. We improve this to with a simpler and…
On the Duality of Semiantichains and Unichain Coverings
Bartłomiej Bosek, Stefan Felsner, Kolja Knauer +1
We study a min-max relation conjectured by Saks and West: For any two posets and the size of a maximum semiantichain and the size of a minimum unichain covering in the prod…
Additive colorings of planar graphs
Tomasz Bartnicki, Bartłomiej Bosek, Sebastian Czerwiński +3
An \emph{additive coloring} of a graph is an assignment of positive integers to the vertices of such that for every two adjacent vertices the sums of number…
On-line Chain Partitions of Up-growing Semi-orders
Stefan Felsner, Kamil Kloch, Grzegorz Matecki +1
On-line chain partition is a two-player game between Spoiler and Algorithm. Spoiler presents a partially ordered set, point by point. Algorithm assigns incoming points (immediately…