Faster and simpler algorithm for sorting signed permutations by reversals

Haim Kaplan; Ron Shamir; Robert E. Tarjan

Faster and simpler algorithm for sorting signed permutations by reversals

Haim Kaplan, Ron Shamir, Robert E. Tarjan

Research output: Contribution to conference › Paper › peer-review

Abstract

We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation of Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

Original language	English (US)
Pages	344-351
Number of pages	8
State	Published - 1997
Event	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA Duration: Jan 5 1997 → Jan 7 1997

Other

Other	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
City	New Orleans, LA, USA
Period	1/5/97 → 1/7/97

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Cite this

@conference{dd0a220cfbbd4f1c8c1a418b9c3ce235,

title = "Faster and simpler algorithm for sorting signed permutations by reversals",

abstract = "We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation of Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.",

author = "Haim Kaplan and Ron Shamir and Tarjan, {Robert E.}",

year = "1997",

language = "English (US)",

pages = "344--351",

note = "Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 05-01-1997 Through 07-01-1997",

}

TY - CONF

T1 - Faster and simpler algorithm for sorting signed permutations by reversals

AU - Kaplan, Haim

AU - Shamir, Ron

AU - Tarjan, Robert E.

PY - 1997

Y1 - 1997

N2 - We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation of Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

AB - We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its faster implementation of Berman and Hannenhalli. The algorithm is conceptually simple and does not require special data structures. Our study also considerably simplifies the combinatorial structures used by the analysis.

UR - http://www.scopus.com/inward/record.url?scp=0030735997&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030735997&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0030735997

SP - 344

EP - 351

T2 - Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 5 January 1997 through 7 January 1997

ER -

Faster and simpler algorithm for sorting signed permutations by reversals

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this