On the tightness of the alternating-cycle lower bound for sorting by reversals

DOI10.1023/A:1009838309166zbMATH Open0960.90074MaRDI QIDQ1306396FDOQ1306396

Authors: Alberto Caprara 

Publication date: 21 November 1999

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Recommendations

• Genome Rearrangements and Sorting by Reversals
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions

zbMATH Keywords

sorting by reversalsalternating-cycle relaxationprobability countingtightness of lower bounds

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cited In (7)

• Estimating the expected reversal distance after a fixed number of reversals
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles?
• A tight amortized bound for path reversal
• On the average number of reversals needed to sort signed permutations
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• Certifying algorithms and relevant properties of reversible primitive permutations with \textsf{Lean}

This page was built for publication: On the tightness of the alternating-cycle lower bound for sorting by reversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306396)