25 citations · 54 across the 7 of their papers we have counts for
10 papers
An Optimal Sorting Algorithm for Persistent Random Comparison Faults
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We consider the problem of sorting elements subject to persistent random comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (…
Longest Increasing Subsequence under Persistent Comparison Errors
Barbara Geissmann
We study the problem of computing a longest increasing subsequence in a sequence of distinct elements in the presence of persistent comparison errors. In this model, every…
Parallel Minimum Cuts in Near-linear Work and Low Depth
Barbara Geissmann, Lukas Gianinazzi
We present the first near-linear work and poly-logarithmic depth algorithm for computing a minimum cut in a graph, while previous parallel algorithms with poly-logarithmic depth re…
Optimal Sorting with Persistent Comparison Errors
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We consider the problem of sorting elements in the case of \emph{persistent} comparison errors. In this model (Braverman and Mossel, SODA'08), each comparison between two eleme…
Sorting by Swaps with Noisy Comparisons
Tomáš Gavenčiak, Barbara Geissmann, Johannes Lengler
We study sorting of permutations by random swaps if each comparison gives the wrong result with some fixed probability . We use this process as prototype for the behaviour o…
Sorting with Recurrent Comparison Errors
Barbara Geissmann, Stefano Leucci, Chih-Hung Liu +1
We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sort…
Sort well with energy-constrained comparisons
Barbara Geissmann, Paolo Penna
We study very simple sorting algorithms based on a probabilistic comparator model. In our model, errors in comparing two elements are due to (1) the energy or effort put in the com…
Collaborative Delivery with Energy-Constrained Mobile Robots
Andreas Bärtschi, Jérémie Chalopin, Shantanu Das +5
We consider the problem of collectively delivering some message from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has a l…
On computing the total displacement number via weighted Motzkin paths
Andreas Bärtschi, Barbara Geissmann, Daniel Graf +3
Counting the number of permutations of a given total displacement is equivalent to counting weighted Motzkin paths of a given area (Guay-Paquet and Petersen, 2014). The former comb…
Counting small cuts in a graph
Barbara Geissmann, Rastislav Šrámek
We study the minimum cut problem in the presence of uncertainty and show how to apply a novel robust optimization approach, which aims to exploit the similarity in subsequent graph…