In this paper, we propose a bio-molecular algorithm with O(n 2 + m) biological operations, O(2 n ) DNA strands, O(n) tubes and the longest DNA strand, O(n), for solving the independent-set problem ...for any graph G with m edges and n vertices. Next, we show that a new kind of the straightforward Boolean circuit yielded from the bio-molecular solutions with m NAND gates, (m + n × (n +1)) AND gates and ((n × (n + 1)) / 2) NOT gates can find the maximal independent-set(s) to the independent-set problem for any graph G with m edges and n vertices. We show that a new kind of the proposed quantum-molecular algorithm can find the maximal independent set(s) with the lower bound O(2 n/2 ) queries and the upper bound Ω(2 n/2 ) queries. This work offers an obvious evidence that to solve the independent-set problem in any graph G with m edges and n vertices, bio-molecular computers are able to generate a new kind of the straightforward Boolean circuit such that by means of implementing it quantum computers can give a quadratic speed-up. This work also offers one obvious evidence that quantum computers can significantly accelerate the speed and enhance the scalability of bio-molecular computers. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with three vertices and two edges by carrying out experiments on the backend ibmqx4 with five quantum bits and the backend simulator with 32 quantum bits on IBM’s quantum computer.
In this paper, we propose a bio-molecular algorithm with O(<inline-formula> <tex-math notation="LaTeX">{n}^{{2}} + {m} </tex-math></inline-formula>) biological operations, O(<inline-formula> ...<tex-math notation="LaTeX">2^{n} </tex-math></inline-formula>) DNA strands, O(<inline-formula> <tex-math notation="LaTeX">{n} </tex-math></inline-formula>) tubes and the longest DNA strand, O(<inline-formula> <tex-math notation="LaTeX">{n} </tex-math></inline-formula>), for solving the independent-set problem for any graph G with <inline-formula> <tex-math notation="LaTeX">{m} </tex-math></inline-formula> edges and <inline-formula> <tex-math notation="LaTeX">{n} </tex-math></inline-formula> vertices. Next, we show that a new kind of the straightforward Boolean circuit yielded from the bio-molecular solutions with <inline-formula> <tex-math notation="LaTeX">{m} </tex-math></inline-formula> NAND gates, (<inline-formula> <tex-math notation="LaTeX">{m} +{n} \times </tex-math></inline-formula> (<inline-formula> <tex-math notation="LaTeX">{n} + {1} </tex-math></inline-formula>)) AND gates and ((<inline-formula> <tex-math notation="LaTeX">{n} \times </tex-math></inline-formula> (<inline-formula> <tex-math notation="LaTeX">{n} + {1} </tex-math></inline-formula>))/2) NOT gates can find the maximal independent-set(s) to the independent-set problem for any graph <inline-formula> <tex-math notation="LaTeX">{G} </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">{m} </tex-math></inline-formula> edges and <inline-formula> <tex-math notation="LaTeX">{n} </tex-math></inline-formula> vertices. We show that a new kind of the proposed quantum-molecular algorithm can find the maximal independent set(s) with the lower bound <inline-formula> <tex-math notation="LaTeX">\Omega </tex-math></inline-formula>(<inline-formula> <tex-math notation="LaTeX">2^{n/{2}} </tex-math></inline-formula>) queries and the upper bound O(<inline-formula> <tex-math notation="LaTeX">2^{n/{2}} </tex-math></inline-formula>) queries. This work offers an obvious evidence for that to solve the independent-set problem in any graph <inline-formula> <tex-math notation="LaTeX">{G} </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">{m} </tex-math></inline-formula> edges and <inline-formula> <tex-math notation="LaTeX">{n} </tex-math></inline-formula> vertices, bio-molecular computers are able to generate a new kind of the straightforward Boolean circuit such that by means of implementing it quantum computers can give a quadratic speed-up. This work also offers one obvious evidence that quantum computers can significantly accelerate the speed and enhance the scalability of bio-molecular computers. Next, the element distinctness problem with input of <inline-formula> <tex-math notation="LaTeX">{n} </tex-math></inline-formula> bits is to determine whether the given <inline-formula> <tex-math notation="LaTeX">2^{n} </tex-math></inline-formula> real numbers are distinct or not. The quantum lower bound of solving the element distinctness problem is <inline-formula> <tex-math notation="LaTeX">\Omega </tex-math></inline-formula>(<inline-formula> <tex-math notation="LaTeX">2^{n\times {(}{2}/{3}{)}} </tex-math></inline-formula>) queries in the case of a quantum walk algorithm. We further show that the proposed quantum-molecular algorithm reduces the quantum lower bound to <inline-formula> <tex-math notation="LaTeX">\Omega </tex-math></inline-formula>((<inline-formula> <tex-math notation="LaTeX">2^{n/{2}} </tex-math></inline-formula>)/(<inline-formula> <tex-math notation="LaTeX">2^{\text {1/2}}{)} </tex-math></inline-formula>) queries. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with two vertices and one edge by carrying out experiments on the backend ibmqx4 with five quantum bits and the backend simulator with 32 quantum bits on IBM's quantum computer.
In this paper, we consider a maximum weighted k distance-d independent set problem, which is a variant of maximum weighted distance-d independent set problems, on interval graph. We propose a ...pseudo-polynomial time algorithm for maximum weighted k distance-d independent set problems on interval graphs, based on a solution to an exact weighted independent set problem. In addition, the performance of the proposed algorithm was evaluated by computational experiments. According to the experiments, it is found that the parameter k has a significant influence on the calculation time compared with parameters d, k
