西安电子科技大学学报（自然科学版）
西安電子科技大學學報（自然科學版）
서안전자과기대학학보（자연과학판）
JOURNAL OF XIDIAN UNIVERSITY(NATURAL SCIENCE)
2013年
5期
175-180
,共6页
朱维军%徐朝辉%张海宾%杨卫东
硃維軍%徐朝輝%張海賓%楊衛東
주유군%서조휘%장해빈%양위동
有向图%脱氧核糖核酸%时间复杂度%粘贴系统
有嚮圖%脫氧覈糖覈痠%時間複雜度%粘貼繫統
유향도%탈양핵당핵산%시간복잡도%점첩계통
directed graphs%DNA%time complexity%sticker systems
针对经典计算的有向图k边导出子图生成算法时间复杂度较高问题,提出了一种在脱氧核糖核酸粘贴机上运行的子图生成算法.首先,以粘贴系统提供的标准生化元操作为算法使用的基本元算子,并使用元操作所产生的生化结果的图论解释作为元算子的最小语义单元;其次,使用包括顺序、循环等在内的程序控制结构,设计一定的逻辑方式把元算子组织起来,以计算有向图导出子图.复杂度分析表明,新算法可在线性时间生成所有子图.仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅降低了子图生成时间.
針對經典計算的有嚮圖k邊導齣子圖生成算法時間複雜度較高問題,提齣瞭一種在脫氧覈糖覈痠粘貼機上運行的子圖生成算法.首先,以粘貼繫統提供的標準生化元操作為算法使用的基本元算子,併使用元操作所產生的生化結果的圖論解釋作為元算子的最小語義單元;其次,使用包括順序、循環等在內的程序控製結構,設計一定的邏輯方式把元算子組織起來,以計算有嚮圖導齣子圖.複雜度分析錶明,新算法可在線性時間生成所有子圖.倣真實驗結果錶明,與經典算法相比,新算法在理想條件下大幅降低瞭子圖生成時間.
침대경전계산적유향도k변도출자도생성산법시간복잡도교고문제,제출료일충재탈양핵당핵산점첩궤상운행적자도생성산법.수선,이점첩계통제공적표준생화원조작위산법사용적기본원산자,병사용원조작소산생적생화결과적도론해석작위원산자적최소어의단원;기차,사용포괄순서、순배등재내적정서공제결구,설계일정적라집방식파원산자조직기래,이계산유향도도출자도.복잡도분석표명,신산법가재선성시간생성소유자도.방진실험결과표명,여경전산법상비,신산법재이상조건하대폭강저료자도생성시간.
