57 citations · 130 across the 9 of their papers we have counts for
11 papers
Prefix reversals on binary and ternary strings
Cor Hurkens, Leo van Iersel, Judith Keijsper +3
Given a permutation pi, the application of prefix reversal f^(i) to pi reverses the order of the first i elements of pi. The problem of Sorting By Prefix Reversals (also known as p…
On the Complexity of the Single Individual SNP Haplotyping Problem
Rudi Cilibrasi, Leo van Iersel, Steven Kelk +1
We present several new results pertaining to haplotyping. These results concern the combinatorial problem of reconstructing haplotypes from incomplete and/or imperfectly sequenced…
On the Complexity of Several Haplotyping Problems
Rudi Cilibrasi, Leo van Iersel, Steven Kelk +1
In this paper we present a collection of results pertaining to haplotyping. The first set of results concerns the combinatorial problem of reconstructing haplotypes from incomplete…
Limits of Rush Hour Logic Complexity
John Tromp, Rudi Cilibrasi
Rush Hour Logic was introduced in [Flake&Baum99] as a model of computation inspired by the ``Rush Hour'' toy puzzle, in which cars can move horizontally or vertically within a park…
Sharpening Occam's Razor
Ming Li, John Tromp, Paul Vitanyi
We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to: (i) Obtain better sample comple…
Kolmogorov Random Graphs and the Incompressibility Method
Harry Buhrman, Ming Li, John Tromp +1
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressib…