Reversal distance for strings with duplicates: linear time approximation using hitting set.

Kolman, Petr; Walen, Tomasz

Displaying similar documents to “Reversal distance for strings with duplicates: linear time approximation using hitting set.”

Minimum common string partition problem: hardness and approximations.

Goldstein, Avraham, Kolman, Petr, Zheng, Jie (2005)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Worst case analysis of two heuristics for the set partitioning problem

A. Marchetti Spaccamela, A. Pelaggi (1987)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Evaluating the Kernighan-Lin heuristic for hardware/software partitioning

Zoltán Mann, András Orbán, Viktor Farkas (2007)

International Journal of Applied Mathematics and Computer Science

Similarity:

In recent years, several heuristics have been proposed for the hardware/software partitioning problem. One of the most promising directions is the adaptation of the Kernighan-Lin algorithm. The Kernighan-Lin heuristic was originally developed for circuit partitioning, but it has been adapted to other domains as well. Moreover, numerous improvements have been suggested so that now several variants of the original algorithm exist. The aim of this paper is to systematically evaluate the...

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We present a CAT (constant amortized time) algorithm for generating those partitions of that are in the ${IPM}_{k}$ (), a generalization of the $SPM$ (). More precisely, for any fixed integer , we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice ${IPM}_{k}$ (): this lets us design an algorithm which generates all the ice piles of ${IPM}_{k}$ () in amortized time (1) and in space ( $\sqrt{n}$ ).

A sparse dynamic programming algorithm for alignment with non-overlapping inversions

Alair Pereira Do Lago, Ilya Muchnik, Casimir Kulikowski (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions...

Tuning the Zhu-Takaoka string matching algorithm and experimental results

Thomas Berry, Somasundaram Ravindran (2002)

Kybernetika

Similarity:

In this paper we present experimental results for string matching algorithms which have a competitive theoretical worst case run time complexity. Of these algorithms a few are already famous for their speed in practice, such as the Boyer–Moore and its derivatives. We chose to evaluate the algorithms by counting the number of comparisons made and by timing how long they took to complete a given search. Using the experimental results we were able to introduce a new string matching algorithm...

Some results on the $m (4)$ problem of Erdös and Hajnal.

Manning, Gregory M. (1995)

Electronic Research Announcements of the American Mathematical Society [electronic only]

Similarity:

A new practical linear space algorithm for the longest common subsequence problem

Heiko Goeman, Michael Clausen (2002)

Kybernetika

Similarity:

This paper deals with a new practical method for solving the longest common subsequence (LCS) problem. Given two strings of lengths $m$ and $n$ , $n \geq m$ , on an alphabet of size $s$ , we first present an algorithm which determines the length $p$ of an LCS in $O (n s + min {m p, p (n - p)})$ time and $O (n s)$ space. This result has been achieved before [ric94,ric95], but our algorithm is significantly faster than previous methods. We also provide a second algorithm which generates an LCS in $O (n s + min {m p, m log m + p (n - p)})$ time while preserving the linear space bound,...