检索结果-南通市图书馆

The (⊿+2,2)-incidence coloring of outerplanar graphs

Progress in Natural science:Materials International 2008年第5期18卷 575-578页

作者： Shudong Wanga,b,c, Jin Xu a,b, Fangfang Mac, Chunxiang Xua,b a Institute of Software, School of Electronic Engineering and Computer science, Peking University, Beijing 100871, china b Key Laboratory of High Con dence Software Technologies, Ministry of Education, Beijing 100871, china c College of Information science and Engineering, Shandong University of science and Technology, Qingdao 266510, china Institute of Software School of Electronic Engineering and Computer Science Peking University Beijing 100871 China Key Laboratory of High Confidence Software Technologies Ministry of Education Beijing 100871 China College of Information science and Engineering Shandong University of Science and Technology Qingdao 266510 China

An incidence coloring of graph G is a coloring of its incidences in which neighborly incidences are assigned di erent colors. In this paper, the incidence coloring of outerplanar graphs is discussed using the techniques of exchanging colors and the double inductions from the aspect of con guration property. Results show that there exists a (D + 2,2)-incidence coloring in every outerplanar graph, where D is the maximum degree of outerplanar graph.

关键词： Incidence coloring Incidence chromatic number Outerplanar graph

来源：

同方期刊数据库评论

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

A novel computing model of the maximum clique problem based on circular DNA

引用

science china(Information sciences) 2010年第7期53卷 1409-1416页

作者： YANG Jing, ZHANG Cheng, XU Jin*, LIU XiangRong & QIANG XiaoLi Institute of Software, School of Electronics Engineering and Computer science, Key Laboratory of High Confidence Software Technologies, Ministry of Education, Peking University, Beijing 100871, china Institute of Software School of Electronics Engineering and Computer Science Key Laboratory of High Confidence Software Technologies Ministry of Education Peking University Beijing China

A novel DNA-based model is developed to calculate NP-complete problems, which is made of circular DNA molecules, streptavidin-coated magnetic beads and DNA circligase. To test the feasibility of the model, we apply it to compute a five-node maximum clique problem (MCP). During the computation, DNA molecule structures were transformed between linear DNA and circular DNA by streptavidin-coated magnetic beads and circligase, in order to search for the truth solutions. This greatly reduces the quantity of time and space consumed in calculation, and its time and space complexity both are O(n + m). Compared with the brute force method, using this algorithm searching process at most needs in n + 1 test tubes for an MCP with n vertices, while brute force method requires 2n test tubes. Furthermore, the constructed unenumerable initial solution space greatly improved the processing ability of the DNA computer. This novel model indicates that it may be a powerful DNA-based computer for solving some NP-complete problems.

关键词： DNA-based computing model circular DNA molecules NP-complete problem circligase streptavidin-coated magnetic beads

来源：

同方期刊数据库评论

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

A DNA length reducing computing model for maximum independent set problem

引用

Chinese science Bulletin 2010年第9期55卷 892-898页

作者： Zhang Cheng Yang Jing Xu Jin Zhao DongMing Peking Univ Key Lab High Confidence Software Technol Sch Elect Engn & Comp Sci Inst SoftwareMinist Educ Beijing 100871 Peoples R China

In this paper, a new molecular computing model is developed to solve the maximum independent set problem, based on the method of DNA length reducing. To solve the maximum independent set problem with n-vertices and m-edges, the time complexity is O(n+m). With the enlargement of the problem scale, the numbers of the required tubes will increase linearly. Two important methods in this experiment are single strand DNA (ssDNA) circularization and DNA length reducing. In addition, using reverse polymerase chain reaction (PCR) and circligase, the structure of DNA molecules is changed in each computing step, transforming from linear double strand DNA (dsDNA) to linear ssDNA and circular ssDNA. Using the circular DNA structure, the recombina-tion among DNA molecules is avoided. To verify this computing model, a small maximum independent set problem was solved.

关键词： NP-complete problem reverse PCR linear ssDNA circularization DNA length reducing

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

DNA计算中荧光技术的应用及其发展

引用

计算机学报 2009年第12期32卷 2300-2310页

作者：张成杨静王淑栋北京大学信息科学技术学院高可信度软件技术教育部重点实验室北京100871

DNA计算作为前沿科学研究的重点和热点,已经从简单发展为复杂,从理论转化为应用.在这一过程中,反应速度快、变化灵敏的荧光标记技术发挥了重要的作用.文中围绕DNA计算和荧光标记技术两个方面进行说明.一方面,对近年来DNA计算中荧光技术... 详细信息

DNA计算作为前沿科学研究的重点和热点,已经从简单发展为复杂,从理论转化为应用.在这一过程中,反应速度快、变化灵敏的荧光标记技术发挥了重要的作用.文中围绕DNA计算和荧光标记技术两个方面进行说明.一方面,对近年来DNA计算中荧光技术的应用进行了总结:(1)荧光标记的表面计算;(2)与某些酶切技术相结合的荧光检测;(3)与DNA链置换相结合的荧光技术;(4)与基因沉默技术相结合的荧光DNA逻辑门;(5)与DNA自组装立体结构相结合的荧光技术;(6)与DNA变构相结合的荧光技术.另一方面,介绍了几种近年来发展起来的新型荧光技术:(1)荧光信号识别放大技术;(2)与磁珠技术相结合的荧光技术;(3)与PH值变化相结合的DNA荧光技术;(4)与miRNAs检测相结合的荧光技术.在今后的研究中,只有将这两者紧密结合,才能发挥DNA计算天然的优势.

关键词： DNA计算荧光标记技术纳米技术 DNA分子杂交

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：