Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Prefix Block-Interchanges on Binary Strings
View through CrossRef
A block-interchange acting on a string s exchanges two non-overlapping but not necessary adjacent substrings in s. A prefix block-interchange is a special block-interchange in which one of the two exchanged substrings is restricted to a prefix of s. In this study, we study the problem of sorting by prefix block-interchanges on binary strings, which is to find the minimum number of prefix block-interchanges to sort a given binary string. In addition, we study the problem of computing the prefix block-interchange distance between two binary strings, which is to compute the minimum number of prefix block-interchanges to transform a given binary string into another given binary string. Consequently, we design a linear-time algorithm to solve the problem of sorting by prefix block-interchange on binary strings and also show that the problem of computing the prefix block-interchange distance between two binary strings is NP-hard.
Title: Prefix Block-Interchanges on Binary Strings
Description:
A block-interchange acting on a string s exchanges two non-overlapping but not necessary adjacent substrings in s.
A prefix block-interchange is a special block-interchange in which one of the two exchanged substrings is restricted to a prefix of s.
In this study, we study the problem of sorting by prefix block-interchanges on binary strings, which is to find the minimum number of prefix block-interchanges to sort a given binary string.
In addition, we study the problem of computing the prefix block-interchange distance between two binary strings, which is to compute the minimum number of prefix block-interchanges to transform a given binary string into another given binary string.
Consequently, we design a linear-time algorithm to solve the problem of sorting by prefix block-interchange on binary strings and also show that the problem of computing the prefix block-interchange distance between two binary strings is NP-hard.
Related Results
Prefix Block-Interchanges on Binary and Ternary Strings
Prefix Block-Interchanges on Binary and Ternary Strings
Abstract
The genome rearrangement problem computes the minimum number of operations that are required to sort all elements of a permutation. A block-interchange ope...
AFIKSASI DALAM PENINGKATAN VALENSI VERBA BAHASA JAWA DAN BAHASA BANJAR
AFIKSASI DALAM PENINGKATAN VALENSI VERBA BAHASA JAWA DAN BAHASA BANJAR
Abstrak
Penelitian ini merupakan penelitian kualitatif yang bertujuan untuk untuk mengetahui proses afiksasi yang berperan terhadap peningkatan valensi verba dalam bahasa Jaw...
Parameterized Strings: Algorithms and Applications
Parameterized Strings: Algorithms and Applications
The parameterized string (p-string), a generalization of the traditional string, is composed of constant and parameter symbols. A parameterized match (p-match) exists between two p...
Safety Analysis of Interchanges
Safety Analysis of Interchanges
As the U.S. freeway system ages and becomes more congested, many parts of the system, particularly interchanges, need reconstruction or rehabilitation. In addition, new development...
Study of Affixation In West Simeulue Language
Study of Affixation In West Simeulue Language
This study discusses the type of affixation, especially prefixes and suffixes in the West Simeulue language. This study aims to find what types of prefixes and suffixes are in West...
Design of Casing Strings
Design of Casing Strings
Abstract
Considerable economy can be effected by designing each casing string individually for the particular set of conditions involved. The paper discusses meth...
Low Power Parallel Prefix Adder
Low Power Parallel Prefix Adder
Addition is a fundamental operation of all Arithmetic and Logic Units (ALU).The speed of addition operation decides the computational frequency of ALU. In order to improve the perf...
BINARY TOPOLOGY BASED ON SOME NEW SETS
BINARY TOPOLOGY BASED ON SOME NEW SETS
In this chapter, we introduce and some new sets called binary -open sets, binary -sets, binary -sets, binary -closed sets, binary -sets and binary -sets , which are simple forms of...