【摘要】：最大圈分解問題最早由Erd銉s和Pósa提出,隨后研究人員在圖論領(lǐng)域和理論計算機科學領(lǐng)域中對其進行了廣泛的探索。最近研究發(fā)現(xiàn),該問題在計算生物學上特別是在構(gòu)建進化樹與分析基因組的研究方面有重要的應用。主要介紹了該問題的研究現(xiàn)狀。首先討論了該問題在圖論方面的研究進展;隨后對該問題的近似算法、參數(shù)算法、參數(shù)復雜性與不可近似性進行了分析和討論;最后給出了該問題的進一步研究方向。
[Abstract]:The problem of maximum cycle decomposition was first proposed by Erd s and P 貿(mào) sa, and then widely explored by researchers in the field of graph theory and theoretical computer science. Recent studies have found that this problem has important applications in computational biology, especially in the research of constructing evolutionary trees and analyzing genomes. This paper mainly introduces the research status of this problem. This paper first discusses the research progress of the problem in graph theory, then analyzes and discusses the approximate algorithm of the problem, parameter complexity and inapproximation, and finally gives the further research direction of the problem.
【作者單位】： 中南大學信息科學與工程學院;
【基金】：國家自然科學基金(61402054,61502054,61370172)資助
【分類號】：TP301.6;O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 魏麒;蔣義偉;;一類兩階段雜交流水作業(yè)的近似算法(英文)[J];軟件學報;2012年05期

2 劉振宏;組合最優(yōu)化問題的近似算法[J];數(shù)學的實踐與認識;1983年03期

3 馬紹漢;一類限制樹問題的復雜性及其近似算法[J];山東大學學報(自然科學版);1984年01期

4 楊延齡,戚文發(fā);關(guān)于最優(yōu)備件問題的近似算法的研究[J];工程數(shù)學學報;1989年01期

5 杜林古;;帶風向投遞員問題的一個多項式1—近似算法[J];山東紡織工學院學報;1992年01期

6 蘇純潔;帶服務(wù)器的三臺平行機排序問題的復雜性和近似算法[J];應用數(shù)學學報;2003年03期

7 劉光聰;朱大銘;姜海濤;;有向基因組反轉(zhuǎn)和轉(zhuǎn)位排序最小權(quán)重問題的1.5k近似算法[J];小型微型計算機系統(tǒng);2010年07期

8 何勇;帶核集分劃問題的一個線性(1/7)-近似算法[J];高校應用數(shù)學學報A輯(中文版);1997年04期

9 季敏,何勇;帶核集分劃問題的一個改進近似算法[J];系統(tǒng)工程理論與實踐;2003年12期

10 何曉瓊;陳沖;李榮珩;;工廠地址集中的k-種產(chǎn)品選址問題的近似算法[J];計算機工程與應用;2010年08期

相關(guān)會議論文 前9條

1 劉聲田;朱大銘;;基因序列翻轉(zhuǎn)排序的一種近似算法[A];山東省計算機學會2005年信息技術(shù)與信息化研討會論文集（一）[C];2005年

2 梅生偉;洪奕光;秦化淑;翁紹鵬;;非線性H_∞控制的粘性解及其近似算法[A];1996年中國控制會議論文集[C];1996年

3 田世俊;李建;朱洪;;多需求目標的UFL問題及其近似算法[A];2005年全國理論計算機科學學術(shù)年會論文集[C];2005年

4 梁國宏;郭云霞;鄭明發(fā);;最大化下模函數(shù)的近似算法及其性能保證[A];第十屆中國不確定系統(tǒng)年會、第十四屆中國青年信息與管理學者大會論文集[C];2012年

5 保利勇;趙東風;丁洪偉;;雙服務(wù)器異步控制策略輪詢系統(tǒng)性能的近似算法分析[A];2009年中國高校通信類院系學術(shù)研討會論文集[C];2009年

6 任建峰;張玉忠;孫國;;一種新的柔性車間排序問題[A];中國企業(yè)運籌學學術(shù)交流大會論文集[C];2005年

7 李灝;張春路;丁國良;;對多層墻體反應系數(shù)的一種近似算法的討論[A];上海市制冷學會一九九七年學術(shù)年會論文集[C];1997年

8 李灝;張春路;丁國良;;對多層墻體反應系數(shù)的一種近似算法的討論[A];全國暖通空調(diào)制冷1998年學術(shù)年會論文集（2）[C];1998年

9 周露;吳瑤華;黃文虎;聞新;;一種推廣卡爾曼濾波的近似算法[A];1995中國控制與決策學術(shù)年會論文集[C];1995年

相關(guān)重要報紙文章 前1條

1 PALADIN;近似算法[N];電腦報;2003年

相關(guān)博士學位論文 前5條

1 楊朝霞;超圖嵌入圈問題的近似算法[D];山東大學;2010年

2 潘銳;設(shè)施選址與K-中間點問題的復雜性與近似算法[D];山東大學;2007年

3 陳仕平;若干組合優(yōu)化問題的近似算法設(shè)計與分析[D];浙江大學;2002年

4 柳楠;基因組片段填充問題的算法研究[D];山東大學;2013年

5 姜海濤;基因組比較算法研究[D];山東大學;2011年

相關(guān)碩士學位論文 前10條

1 陳崇琛;多色點集直線劃分的復雜性及其近似算法[D];復旦大學;2014年

2 王敏;基于圖特征的介度中心近似算法研究[D];曲阜師范大學;2015年

3 張亞平;最小賦權(quán)連通k-子圖覆蓋問題的近似算法[D];新疆大學;2015年

4 張永俊;廣義非線性分式規(guī)劃問題的近似算法[D];河南師范大學;2015年

5 朱婷婷;具有不同釋放時間的單機重新排序問題的近似算法[D];蘭州大學;2016年

6 王克紅;均勻限制NP-完備間題及其近似算法設(shè)計[D];云南大學;2016年

7 肖文英;限制版本瓶頸斯坦納樹問題算法研究[D];中南民族大學;2015年

8 李彥杰;連通控制吸收集的近似算法[D];新疆大學;2013年

9 張峰;漫射光化通量的二流四流混合近似算法求解[D];中國氣象科學研究院;2010年

10 劉海;非光滑問題的三次近似算法[D];北京工業(yè)大學;2014年

，

本文編號：2335852