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.展开更多
Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annea...Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.展开更多
Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It...Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It could be extended to solve Chinese postman problem in directed graph. We make these efforts for exploring in optimizing the mixed Chinese postman problem.展开更多
The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that ...The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.展开更多
Two multi-objective programming models are built to describe Pilots’ full flight simulator (FFS) recurrent training (PFRT) problem. There are two objectives for them. One is the best matching of captains and copilots...Two multi-objective programming models are built to describe Pilots’ full flight simulator (FFS) recurrent training (PFRT) problem. There are two objectives for them. One is the best matching of captains and copilots in the same aircraft type. The other is that pilots could attend his training courses at proper month. Usually the two objectives are conflicting because there are copilots who will promote to captains or transfer to other aircraft type and new trainees will enter the company every year. The main theme in the research is to find the final non-inferior solutions of PFRT problem. Graph models are built to help to analyze the problem and we convert the original problem into a longest-route problem with weighted paths. An algorithm is designed with which we can obtain all the non-inferior solutions by a graphic method. A case study is present to demonstrate the effectiveness of the algorithm as well.展开更多
An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other han...An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.展开更多
An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, ...An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, which eliminate the possibility of cycling and the solution of the problem is reached in a finite number of steps. Example to illustrate the method is also included in the paper.展开更多
通过分析欧拉所给出Knight’s Tour Problem的解法,结合哈密尔顿路和哈密尔顿圈的相关知识,得出其解法对应着二部图中的一条哈密尔顿圈.由此再充分利用8×8棋盘所对应的8×8表格的对称性及同格图的特性,对欧拉所给出的Knight’s...通过分析欧拉所给出Knight’s Tour Problem的解法,结合哈密尔顿路和哈密尔顿圈的相关知识,得出其解法对应着二部图中的一条哈密尔顿圈.由此再充分利用8×8棋盘所对应的8×8表格的对称性及同格图的特性,对欧拉所给出的Knight’s Tour Problem的解法作了进一步的探讨,得出了以欧拉的解法为基础的以任一棋格为骑士周游起点的另外一系列解法.最后,把Knight’sTour Problem推广到m×n棋盘上,考虑到移动规则的特殊性,利用图论的相关知识,得到3×4,8×16和16×16棋盘上的Knight’s Tour Problem的解法,同时给出8m×8n(m>2,n>2)棋盘上Knight’s Tour Problem的猜想.展开更多
Scheduling sports leagues has drawn significant attention to itself in recent years, as it involves considerable revenue as well as challenging combinatorial optimization problems. A particular class of these problems...Scheduling sports leagues has drawn significant attention to itself in recent years, as it involves considerable revenue as well as challenging combinatorial optimization problems. A particular class of these problems is the Traveling Tournament Problem (TTP) which focuses on minimizing the total traveling distance for teams. In this paper, an efficient simulated annealing approach is presented for TTP which applies two simultaneous and disparate models for the problem in order to search the solutions space more effectively. Also, a computationally efficient modified greedy scheme is proposed for constructing a favorable initial solution for the simulated annealing algorithm. Our computational experiments, carried out on standard instances, demonstrate that this approach competes with previous offered methods in quality of found solutions and their computational time.展开更多
We consider a variation of the maximum bipartite matching problem where each completed task must have at least two agents assigned to it. We give an integer programming formulation for the problem, and prove that the ...We consider a variation of the maximum bipartite matching problem where each completed task must have at least two agents assigned to it. We give an integer programming formulation for the problem, and prove that the basic solutions of LP-relaxation are half-integral. It is shown that a fractional basic solution can be further processed to obtain an optimal solution to the problem.展开更多
Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we ...Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we will show that an unconventional coloring scheme of the edges leads to an NP-complete problem when one intends to determine the optimal number of colors.展开更多
基金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.
基金the National Natural Science Foundation of China (60373089, 60674106, and 60533010)the National High Technology Research and Development "863" Program (2006AA01Z104)
文摘Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.
基金Supported by the National Natural Science Foundation of China(60133010,70071042)
文摘Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It could be extended to solve Chinese postman problem in directed graph. We make these efforts for exploring in optimizing the mixed Chinese postman problem.
文摘The bondage number of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph a domination number greater than the domination number of G. In this paper, we prove that for a 1-planar graph G.
文摘Two multi-objective programming models are built to describe Pilots’ full flight simulator (FFS) recurrent training (PFRT) problem. There are two objectives for them. One is the best matching of captains and copilots in the same aircraft type. The other is that pilots could attend his training courses at proper month. Usually the two objectives are conflicting because there are copilots who will promote to captains or transfer to other aircraft type and new trainees will enter the company every year. The main theme in the research is to find the final non-inferior solutions of PFRT problem. Graph models are built to help to analyze the problem and we convert the original problem into a longest-route problem with weighted paths. An algorithm is designed with which we can obtain all the non-inferior solutions by a graphic method. A case study is present to demonstrate the effectiveness of the algorithm as well.
基金supported by the National Natural Science Foundation of China (Grants Nos. 61072139,61072106,61203303,61003198,61272279,and 61003199)
文摘An evolutionary network driven by dynamics is studied and applied to the graph coloring problem. From an initial structure, both the topology and the coupling weights evolve according to the dynamics. On the other hand, the dynamics of the network are determined by the topology and the coupling weights, so an interesting structure-dynamics co-evolutionary scheme appears. By providing two evolutionary strategies, a network described by the complement of a graph will evolve into several clusters of nodes according to their dynamics. The nodes in each cluster can be assigned the same color and nodes in different clusters assigned different colors. In this way, a co-evolution phenomenon is applied to the graph coloring problem. The proposed scheme is tested on several benchmark graphs for graph coloring.
文摘An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, which eliminate the possibility of cycling and the solution of the problem is reached in a finite number of steps. Example to illustrate the method is also included in the paper.
文摘通过分析欧拉所给出Knight’s Tour Problem的解法,结合哈密尔顿路和哈密尔顿圈的相关知识,得出其解法对应着二部图中的一条哈密尔顿圈.由此再充分利用8×8棋盘所对应的8×8表格的对称性及同格图的特性,对欧拉所给出的Knight’s Tour Problem的解法作了进一步的探讨,得出了以欧拉的解法为基础的以任一棋格为骑士周游起点的另外一系列解法.最后,把Knight’sTour Problem推广到m×n棋盘上,考虑到移动规则的特殊性,利用图论的相关知识,得到3×4,8×16和16×16棋盘上的Knight’s Tour Problem的解法,同时给出8m×8n(m>2,n>2)棋盘上Knight’s Tour Problem的猜想.
文摘Scheduling sports leagues has drawn significant attention to itself in recent years, as it involves considerable revenue as well as challenging combinatorial optimization problems. A particular class of these problems is the Traveling Tournament Problem (TTP) which focuses on minimizing the total traveling distance for teams. In this paper, an efficient simulated annealing approach is presented for TTP which applies two simultaneous and disparate models for the problem in order to search the solutions space more effectively. Also, a computationally efficient modified greedy scheme is proposed for constructing a favorable initial solution for the simulated annealing algorithm. Our computational experiments, carried out on standard instances, demonstrate that this approach competes with previous offered methods in quality of found solutions and their computational time.
文摘We consider a variation of the maximum bipartite matching problem where each completed task must have at least two agents assigned to it. We give an integer programming formulation for the problem, and prove that the basic solutions of LP-relaxation are half-integral. It is shown that a fractional basic solution can be further processed to obtain an optimal solution to the problem.
文摘Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we will show that an unconventional coloring scheme of the edges leads to an NP-complete problem when one intends to determine the optimal number of colors.
