Minimum common string partition problem: hardness and approximations.
Goldstein, Avraham, Kolman, Petr, Zheng, Jie (2005)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Displaying similar documents to “Reversal distance for strings with duplicates: linear time approximation using hitting set.”
Minimum common string partition problem: hardness and approximations.
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 (), a generalization of the (). More precisely, for any fixed integer , we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice (): this lets us design an algorithm which generates all the ice piles of () in amortized time (1) and in space ().
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 problem of Erdös and Hajnal.
Manning, Gregory M. (1995)
Electronic Research Announcements of the American Mathematical Society [electronic only]
Similarity: