Josef Cibulka
Graph sharing games: complexity and connectivity.
Tue, 02/07/2012 - 15:01 — SomNambulAuthors: Josef Cibulka, Pavel Valtr, Jan Kynčl, Viola Mészáros, Rudolf Stolař
Subjects: Discrete Mathematics
AbstractWe study the following combinatorial game played by two players, Alice and
Bob, which generalizes the Pizza game considered by Brown, Winkler and others.
Given a connected graph G with nonnegative weights assigned to its vertices,
the players alternately take one vertex of G in each turn. The first turn is
Alice's. The vertices are to be taken according to one (or both) of the
following two rules: (T) the subgraph of G induced by the taken vertices is
connected during the whole game, (R) the subgraph of G induced by the remaining
vertices is connected during the whole game.Polynomial-time sortable stacks of burnt pancakes.
Mon, 10/04/2010 - 15:01 — SomNambulAuthors: Josef Cibulka, Anthony Labarre
Subjects: Data Structures and Algorithms
AbstractPancake flipping, a famous open problem in computer science, can be
formalised as the problem of sorting a permutation of positive integers using
as few prefix reversals as possible. In that context, a prefix reversal of
length k reverses the order of the first k elements of the permutation. The
burnt variant of pancake flipping involves permutations of signed integers, and
reversals in that case not only reverse the order of elements but also invert
their signs.Average number of flips in pancake sorting.
Fri, 09/11/2009 - 19:13 — SomNambulAuthors: Josef Cibulka
Subjects: Discrete Mathematics
AbstractWe are given a stack of pancakes of different sizes and the only allowed
operation is to take several pancakes from top and flip them. The unburnt
version requires the pancakes to be sorted by their sizes at the end, while in
the burnt version they additionally need to be oriented burnt-side down. We
present an algorithm with the average number of flips, needed to sort a stack
of n burnt pancakes, equal to 7n/4+O(1) and a randomized algorithm for the
unburnt version with at most 17n/12+O(1) flips on average.
User login
