2 citations · 2 across the 2 of their papers we have counts for
7 papers
Strictly In-Place Algorithms for Permuting and Inverting Permutations
Bartłomiej Dudek, Paweł Gawrychowski, Karol Pokorski
We revisit the problem of permuting an array of length according to a given permutation in place, that is, using only a small number of bits of extra storage. Fich, Munro and P…
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
Bartłomiej Dudek, Paweł Gawrychowski
Permutation appears in permutation if there exists a subsequence of that is order-isomorphic to . The natural question is to check if appears in , and if so c…
Generalised Pattern Matching Revisited
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
In the problem of [STOC'94, Muthukrishnan and Palem], we are given a text of length over an alphabet , a patter…
Computing Quartet Distance is Equivalent to Counting 4-Cycles
Bartłomiej Dudek, Paweł Gawrychowski
The quartet distance is a measure of similarity used to compare two unrooted phylogenetic trees on the same set of leaves, defined as the number of subsets of four leaves relat…
Edit Distance between Unrooted Trees in Cubic Time
Bartłomiej Dudek, Paweł Gawrychowski
Edit distance between trees is a natural generalization of the classical edit distance between strings, in which the allowed elementary operations are contraction, uncontraction an…
Slowing Down Top Trees for Better Worst-Case Bounds
Bartłomiej Dudek, Paweł Gawrychowski
We consider the top tree compression scheme introduced by Bille et al. [ICALP 2013] and construct an infinite family of trees on nodes labeled from an alphabet of size , for…