二元序列的赋权对换排序问题

二元序列的赋权对换排序问题

亓兴勤，何志红，赵洪銮

山东大学数学与系统科学学院，山东济南250100

收稿日期:2005-04-19 修回日期:1900-01-01 出版日期:2006-10-24 发布日期:2006-10-24
通讯作者: 亓兴勤

Sorting binary strings with length weighted transpositions

QI Xing-qin, HE Zhi-hong and ZHAO Hong-luan

School of Math. and Systems Sci., Shandong Univ., Jinan 250100, Shandong, China

Received:2005-04-19 Revised:1900-01-01 Online:2006-10-24 Published:2006-10-24
Contact: QI Xing-qin

摘要/Abstract

摘要： 提出了对换排序的赋权模型，定义一个长度为l的对换的费用是f(l)=l^α,α＞0；分别给出了当0＜α＜1和1＜α＜2时，二元序列赋权对换排序问题的近似算法；证明了当α≥2时，起泡排序算法是此问题的精确算法.

关键词: 二元序列, 对换排序, 近似算法

Abstract: The problem of sorting binary strings with lengthweighted transpositions is considered, i.e. the cost of a transposition of length l is f(l)=l^α, α＞0, rather than 1. Approximation algorithms are given for 0＜α＜1 and 1＜α＜2 respectively, and bubble sort is proved to be an exact algorithm for this problem when α≥2. The results have direct applications in computational biology to the field of comparative genomics.

Key words: approximation algorithm , transposition, binary strings

中图分类号:

TP301

亓兴勤,何志红,赵洪銮 . 二元序列的赋权对换排序问题[J]. J4, 2006, 41(1): 82-85 .

QI Xing-qin,HE Zhi-hong and ZHAO Hong-luan . Sorting binary strings with length weighted transpositions[J]. J4, 2006, 41(1): 82-85 .

参考文献

相关文章 9

[1]	蔡裕华,魏凤英*. 度量空间的概率近似算法[J]. J4, 2013, 48(09): 51-55.
[2]	杨朝霞 . 超图嵌入带权重圈的一个2-近似算法[J]. J4, 2008, 43(8): 11-13 .
[3]	杨振光,李曙光,王秀红 . 工件尺寸不同的并行机批调度问题[J]. J4, 2007, 42(4): 63-66 .
[4]	戴珍香,李曙光,亓兴勤 . 波分复用星形单跳网中3信道的传输调度问题[J]. J4, 2007, 42(2): 46-50 .
[5]	亓兴勤,曹静,张晨 . 环型二元序列的赋权对换排序问题[J]. J4, 2007, 42(12): 46-48 .
[6]	李曙光,白淑岩,何志红,亓兴勤 . 圈中t-区间的k-染色问题[J]. J4, 2006, 41(6): 40-42 .
[7]	李曙光,杨振光,何志红 . 多纤波分复用链网与环网中的利润极大化问题[J]. J4, 2006, 41(5): 7-11 .
[8]	李曙光,亓兴勤,何志红 . 环网络中的呼叫接纳控制[J]. J4, 2006, 41(4): 15-19 .
[9]	王继强, . 一类median问题的近似算法研究[J]. J4, 2006, 41(4): 1-03 .

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed