Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum a...Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover’s search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.展开更多
Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each ver...Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V ／ D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γk（G）, is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs GB（n, d） and generalized Kautz digraphs Gg（n, d） are good candidates for interconnection k networks. Denote △k ：=（∑j^k=0 d^j）^-1. F. Tian and J. Xu showed that [n△k] ≤ γk（GB（n,d）） ≤ [n/d^k] and [n△k] ≤ γk（GK（n,d）） ≤ [n/d^k]. In this paper, we prove that every generalized de Bruijn digraph GB（n, d） has the distance k- domination number [n△k] or [n△k] ＋ 1, and the distance k-domination number of every generalized Kautz digraph GK（n, d） bounded above by [n/ （d^k-1 ＋d^k）]. Additionally, we present various sufficient conditions for γk（GB（n, d）） = [n△k] and γk（GK（n, d）） = [n△k].展开更多
The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving th...The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.展开更多
The bondage number b（G） of number of edges whose removal from G number greater than that of G. Denote a nonempty graph G is the smallest results in a graph with domination Pn × Pm the Cartesian product of two p...The bondage number b（G） of number of edges whose removal from G number greater than that of G. Denote a nonempty graph G is the smallest results in a graph with domination Pn × Pm the Cartesian product of two paths Pn and Pm. This paper determines the exact values of b（Pn × P2）, b（Pn × P3）, and b（Pn × P4） for n ≥ 2.展开更多
基金Project supported by the National Natural Science Foundation of China(Grant No.62101600)the Science Foundation of China University of Petroleum,Beijing(Grant No.2462021YJRC008)the State Key Laboratory of Cryptology(Grant No.MMKFKT202109).
文摘Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing.Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems.This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs.To expedite the search process,a quantum algorithm employing Grover’s search is proposed.However,a challenge arises from the unknown number of solutions for the minimum dominating set,rendering direct usage of original Grover’s search impossible.Thus,a swap test method is introduced to ascertain the number of iterations required.The oracle,diffusion operators,and swap test are designed with achievable quantum gates.The query complexity is O(1.414^(n))and the space complexity is O(n).To validate the proposed approach,qiskit software package is employed to simulate the quantum circuit,yielding the anticipated results.
基金Acknowledgements This work was supported in part by the National Natural Science Foundation of China （Grant Nos. 11471210, 11571222, 11601262）.
文摘Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V ／ D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γk（G）, is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs GB（n, d） and generalized Kautz digraphs Gg（n, d） are good candidates for interconnection k networks. Denote △k ：=（∑j^k=0 d^j）^-1. F. Tian and J. Xu showed that [n△k] ≤ γk（GB（n,d）） ≤ [n/d^k] and [n△k] ≤ γk（GK（n,d）） ≤ [n/d^k]. In this paper, we prove that every generalized de Bruijn digraph GB（n, d） has the distance k- domination number [n△k] or [n△k] ＋ 1, and the distance k-domination number of every generalized Kautz digraph GK（n, d） bounded above by [n/ （d^k-1 ＋d^k）]. Additionally, we present various sufficient conditions for γk（GB（n, d）） = [n△k] and γk（GK（n, d）） = [n△k].
基金supported by the National Natural Science Foundation of China(Grant Nos.61806050,61972063,61976050)the Fundamental Research Funds for the Central Universities(2412020FZ030,2412019ZD013,2412019FZ051)Jilin Science and Technology Association(QT202005).
文摘The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.
文摘The bondage number b（G） of number of edges whose removal from G number greater than that of G. Denote a nonempty graph G is the smallest results in a graph with domination Pn × Pm the Cartesian product of two paths Pn and Pm. This paper determines the exact values of b（Pn × P2）, b（Pn × P3）, and b（Pn × P4） for n ≥ 2.
