Approximating Reversal Distance for Strings with Bounded Number of Duplicates

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F05%3A00206164" target="_blank" >RIV/00216208:11320/05:00206164 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Approximating Reversal Distance for Strings with Bounded Number of Duplicates
Original language description
For a string $A=a_1ldots a_n$, a {em reversal} $rho(i,j)$, $1leq i lt leq n$, reverses the order of symbols in the substring $a_ildots a_j$ of $A$. Given two strings, $A$ and $B$, {em sorting by reversals} is the problem of finding the minimum number of reversals that transform the string $A$ into the string $B$. Traditionally, the problem was studied for permutations. We consider a generalization of the problem and allow each symbol to appear at most $k$ times in each string. The main result ofthe paper is a $Theta(k^2)$-approximation algorithm running in time $O(kn)$.
Czech name
—
Czech description
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Mathematical Foundations of Computer Science 2005, proceedings
ISBN
3-540-28702-7
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
—
Publisher name
Springer
Place of publication
Berlin
Event location
Berlin
Event date
Jan 1, 2005
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000232273200050

Similar results(10)