The biggest bottleneck in DNA computing is exponential explosion, in which the DNA molecules used as data in information processing grow exponentially with an increase of problem size. To overcome this bottleneck and ...The biggest bottleneck in DNA computing is exponential explosion, in which the DNA molecules used as data in information processing grow exponentially with an increase of problem size. To overcome this bottleneck and improve the processing speed, we propose a DNA computing model to solve the graph vertex coloring problem. The main points of the model are as follows： The exponential explosion prob- lem is solved by dividing subgraphs, reducing the vertex colors without losing the solutions, and ordering the vertices in subgraphs; and the bio-operation times are reduced considerably by a designed parallel polymerase chain reaction （PCR） technology that dramatically improves the processing speed. In this arti- cle, a 3-colorable graph with 61 vertices is used to illustrate the capability of the DNA computing model. The experiment showed that not only are all the solutions of the graph found, but also more than 99% of false solutions are deleted when the initial solution space is constructed. The powerful computational capability of the model was based on specific reactions among the large number of nanoscale oligonu- cleotide strands. All these tiny strands are operated by DNA self-assembly and parallel PCR. After thou- sands of accurate PCR operations, the solutions were found by recognizing, splicing, and assembling. We also prove that the searching capability of this model is up to 0（3^59）. By means of an exhaustive search, it would take more than 896 000 years for an electronic computer （5 x 10^14 s-1） to achieve this enormous task. This searching capability is the largest among both the electronic and non-electronic computers that have been developed since the DNA computing model was proposed by Adleman＇s research group in 2002 （with a searching capability of 0（2^20））.展开更多
Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing probl...Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.展开更多
In this paper we present some results connected with still open problem of Gauss, negative Pell’s equation and some type graphs.In particular we prove in the Theorem 1 that all real quadratic fields K=Q( ) , generate...In this paper we present some results connected with still open problem of Gauss, negative Pell’s equation and some type graphs.In particular we prove in the Theorem 1 that all real quadratic fields K=Q( ) , generated by Fermat’s numbers with d=Fm+1=22m+1+1,m≥2, have not unique factorization. Theorem 2 give a connection of the Gauss problem with primitive Pythagorean triples. Moreover, in final part of our paper we indicate on some connections of the Gauss problem with odd graphs investigated by Cremona and Odoni in the papper [5].展开更多
The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) t...The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.展开更多
反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用.子集反馈集问题(subset feedback set problem)是...反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用.子集反馈集问题(subset feedback set problem)是反馈集问题的一种更一般化的形式,更加具有普适性和实用性.近年来,这2个问题在计算复杂性上的分类工作已逐步完善,在算法领域也已出现许多重要的突破.相关研究工作分为2个部分进行介绍.第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题,梳理了它们之间的一些重要关系,并介绍了这些问题在一般图上的计算复杂性.第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性,包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类.最后对反馈集和子集反馈集问题的研究现状进行分析和总结,概括了目前主流的研究趋势.展开更多
基金The authors are grateful for the support from the National Natural Science Foundation of China （61632002, 61379059, and 61572046）.
文摘The biggest bottleneck in DNA computing is exponential explosion, in which the DNA molecules used as data in information processing grow exponentially with an increase of problem size. To overcome this bottleneck and improve the processing speed, we propose a DNA computing model to solve the graph vertex coloring problem. The main points of the model are as follows： The exponential explosion prob- lem is solved by dividing subgraphs, reducing the vertex colors without losing the solutions, and ordering the vertices in subgraphs; and the bio-operation times are reduced considerably by a designed parallel polymerase chain reaction （PCR） technology that dramatically improves the processing speed. In this arti- cle, a 3-colorable graph with 61 vertices is used to illustrate the capability of the DNA computing model. The experiment showed that not only are all the solutions of the graph found, but also more than 99% of false solutions are deleted when the initial solution space is constructed. The powerful computational capability of the model was based on specific reactions among the large number of nanoscale oligonu- cleotide strands. All these tiny strands are operated by DNA self-assembly and parallel PCR. After thou- sands of accurate PCR operations, the solutions were found by recognizing, splicing, and assembling. We also prove that the searching capability of this model is up to 0（3^59）. By means of an exhaustive search, it would take more than 896 000 years for an electronic computer （5 x 10^14 s-1） to achieve this enormous task. This searching capability is the largest among both the electronic and non-electronic computers that have been developed since the DNA computing model was proposed by Adleman＇s research group in 2002 （with a searching capability of 0（2^20））.
文摘Let be an undirected graph. The maximum cycle packing problem in G then is to find a collection of edge-disjoint cycles C<sub>i</sup>in G such that s is maximum. In general, the maximum cycle packing problem is NP-hard. In this paper, it is shown for even graphs that if such a collection satisfies the condition that it minimizes the quantityon the set of all edge-disjoint cycle collections, then it is a maximum cycle packing. The paper shows that the determination of such a packing can be solved by a dynamic programming approach. For its solution, an-shortest path procedure on an appropriate acyclic networkis presented. It uses a particular monotonous node potential.
文摘In this paper we present some results connected with still open problem of Gauss, negative Pell’s equation and some type graphs.In particular we prove in the Theorem 1 that all real quadratic fields K=Q( ) , generated by Fermat’s numbers with d=Fm+1=22m+1+1,m≥2, have not unique factorization. Theorem 2 give a connection of the Gauss problem with primitive Pythagorean triples. Moreover, in final part of our paper we indicate on some connections of the Gauss problem with odd graphs investigated by Cremona and Odoni in the papper [5].
文摘The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.
文摘反馈集问题(feedback set problem)是计算机科学中研究最为广泛和深入的图上NP完全问题之一,其在并发计算、大规模集成电路、编码设计、软件验证、社交网络分析等领域均存在重要的应用.子集反馈集问题(subset feedback set problem)是反馈集问题的一种更一般化的形式,更加具有普适性和实用性.近年来,这2个问题在计算复杂性上的分类工作已逐步完善,在算法领域也已出现许多重要的突破.相关研究工作分为2个部分进行介绍.第1部分详尽地介绍了反馈集和子集反馈集各种不同版本的问题,梳理了它们之间的一些重要关系,并介绍了这些问题在一般图上的计算复杂性.第2部分系统性地介绍了反馈集和子集反馈集问题在一些重要子图类上的计算复杂性,包括度有界的图类、平面图类、竞赛图图类、相交图类、禁止图图类和二部图图类.最后对反馈集和子集反馈集问题的研究现状进行分析和总结,概括了目前主流的研究趋势.
