On the Cost of Interchange Rearrangement in Strings

DOI10.1137/080712969zbMath1209.68390OpenAlexW2088019665MaRDI QIDQ5901157

Oren Kapah, Ely Porat, Tzvika Hartman, Avivit Levy, Amihood Amir

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080712969

zbMATH Keywords

string rearrangement metricsrearrangement cost modelsinterchange distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

Exploiting pseudo-locality of interchange distance ⋮ On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling ⋮ Token Swapping on Trees ⋮ The transposition median problem is NP-complete ⋮ Using swaps and deletes to make strings match ⋮ Approximate string matching with stuck address bits

This page was built for publication: On the Cost of Interchange Rearrangement in Strings