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

DOI10.1023/A:1009838309166zbMath0960.90074MaRDI QIDQ1306396

Alberto Caprara

Publication date: 21 November 1999

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

zbMATH Keywords

sorting by reversalsalternating-cycle relaxationprobability countingtightness of lower bounds

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

Estimating the expected reversal distance after a fixed number of reversals ⋮ Can a breakpoint graph be decomposed into none other than 2-cycles? ⋮ On the average number of reversals needed to sort signed permutations ⋮ Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles?

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