Quantum algorithm for minimum dominating set problem with circuit design

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.

A Game Theoretic Approach for a Minimal Secure Dominating Set

The secure dominating set(SDS),a variant of the dominating set,is an important combinatorial structure used in wireless networks.In this paper,we apply algorithmic game theory to study the minimum secure dominating set(Min SDS) problem in a multi-agent system.We design a game framework for SDS and show that every Nash equilibrium(NE) is a minimal SDS,which is also a Pareto-optimal solution.We prove that the proposed game is an exact potential game,and thus NE exists,and design a polynomial-time distributed local algorithm which converges to an NE in O(n) rounds of interactions.Extensive experiments are done to test the performance of our algorithm,and some interesting phenomena are witnessed.

On the Maximum Number of Dominating Classes in Graph Coloring

We investigate the dominating-c-color number,, of a graph G. That is the maximum number of color classes that are also dominating when G is colored using colors. We show that where is the join of G and . This result allows us to construct classes of graphs such that and thus provide some information regarding two questions raised in [1] and [2].

一种有效的海量数据Top-k Dominating查询算法

在多准则决策支持等多个应用中,top-k dominating查询是一种十分实用的查询,它在潜在的巨大的数据空间中返回k个支配分数最大的元组.现有算法,要么需要为特定的属性组合构建索引,要么需要较大的I/O费用或内存费用,从而无法有效处理海量数据上top-k dominating查询.文中提出一种新的查询算法TDEP,该算法利用以较小代价为每个属性构建的有序列表来有效返回海量数据上的top-k dominating查询结果.文中将TDEP算法的执行明确地分为两个阶段:增长阶段和收缩阶段.在每个阶段,TDEP算法以round-robin方式读取涉及到的有序列表并维护候选元组,直到满足结束条件.文中分析了两个阶段的执行行为,提出一种新的不需要重新读取有序列表的支配分数计算方法.同时,文中还提出有效的早剪切操作,可以有效减少TDEP算法需要维护的候选元组数量.实验结果表明:和现有算法相比,TDEP算法具有较大的性能优势.

无爪图中的次和与Dominating最长路

设H为一图.H中由m个点组成的独立集和由m个点组成的割集分别称为m-独立集和m-割集,而经过v∈V（H）的圈v-圈.设D为H的子图,测|D|和H-D分别表示|V（D）|（D的阶）和H-V（D）.称H是无爪的,如果它不含K1,3作为导出子图.称H是m-路连通的（m≥1）,如果|H|≥2,H的任一对点都由长度≥m的路相联.称只有一个点的图为0-路连通的.H中的路R是一dominating路,如果R是Hamilton的,或者V（H-R）是一独立点集.对H的子图A和D。

图论中图的Dominating圈的存在

本文作者采用构造分析的方法研究并得到了一类非Dominating圈图的结构。在此基础上就图的两个参数研究了图的Dominating圈的存在,得到一些关于Dominating圈存在的新结果,扩大了Dominating圈图的范围,而且这些结果均比Veldman得到的更好。主要结果为:设图G是具有n(≥5)个顶点的简单图,如果对于G的任意一对分离的边e,f及对V(G)的任意非空子集S d(e)+d(f)≥n-3及ω_1(G-S)≤|S|则图G是Dominating圈图。

子图的度与 Dominating 圈

笔者利用子图的度给出了如下结果：对2-连通无爪图 G，若任意同构于 K2的不相邻子图 H1，H2，H3满足：d（H1）＋d（H2）＋d（H3）≥｜G｜-1，则 G 的任意最长圈是 Dominating 圈。

Diversity of Pareto front: A multiobjective genetic algorithm based on dominating information

In this paper, the diversity information included by dominating number is analyzed, and the probabilistic relationship between dominating number and diversity in the space of objective function is proved. A ranking method based on dominating number is proposed to build the Pareto front. Without increasing basic Pareto method’s computation complexity and introducing new parameters, a new multiobjective genetic algorithm based on proposed ranking method (MOGA-DN) is presented. Simulation results on function optimization and parameters optimization of control system verify the efficiency of MOGA-DN.

Minimum Dominating Tree Problem for Graphs

A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.

Dominating factors on well productivity and development strategies optimization in Weiyuan shale gas play, Sichuan Basin, SW China

Weiyuan shale gas play is characterized by thin high-quality reservoir thickness,big horizontal stress difference,and big productivity differences between wells.Based on integrated evaluation of shale gas reservoir geology and well logging interpretation of more than 20 appraisal wells,a correlation was built between the single well test production rate and the high-quality reservoir length drilled in the horizontal wells,high-quality reservoir thickness and the stimulation treatment parameters in over 100 horizontal wells,the dominating factors on horizontal well productivity were found out,and optimized development strategies were proposed.The results show that the deployed reserves of high-quality reservoir are the dominating factors on horizontal well productivity.In other words,the shale gas well productivity is controlled by the thickness of the high-quality reservoir,the high-quality reservoir drilling length and the effectiveness of stimulation.Based on the above understanding,the development strategies in Weiyuan shale gas play are optimized as follows:(1)The target of horizontal wells is located in the middle and lower parts of Longyi 11(Wei202 area)and Longyi 11(Wei204 area).(2)Producing wells are drilled in priority in the surrounding areas of Weiyuan county with thick high-quality reservoir.(3)A medium to high intensity stimulation is adopted.After the implementation of these strategies,both the production rate and the estimated ultimate recovery(EUR)of individual shale gas wells have increased substantially.

Applying Surface-Based DNA Computing for Solving the Dominating Set Problem

The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.

The Middle Equitable Dominating Graphs

Let G= (V, E) be a graph and A(G) is the collection of all minimal equitable dominating set of G. The middle equitable dominating graph of G is the graph denoted by Med(G) with vertex set the disjoint union of V∪A(G) and (u, v) is an edge if and only if u ∩ v ≠ φ whenever u, v ∈ A(G) or u ∈ v whenever u ∈ v and v ∈ A(G) . In this paper, characterizations are given for graphs whose middle equitable dominating graph is connected and Kp∈Med(G) . Other properties of middle equitable dominating graphs are also obtained.

Unique Efficient Dominating Sets

Given a finite simple graph G, a set D ⊆V(G) is called a dominating set if for all v ∈ V(G) , either v ∈ D or v is adjacent to some vertex in D. A dominating set D is independent if none of the vertices in D are adjacent, and D is perfect if each vertex not in D is adjacent to precisely one vertex in D. If a dominating set is both independent and perfect, then it is called an efficient dominating set. For a graph G, a set D is called a unique efficient dominating set of G if it is the only efficient dominating set of G. In this paper, the authors propose the definition of unique efficient dominating set, explore the properties of graphs with unique efficient dominating sets, and completely characterize several families of graphs which have unique efficient dominating sets.

Do Almost All Trees Have No Perfect Dominating Set?

A graph G is said to have a perfect dominating set S if S is a set of vertices of G and for each vertex v of G, either v is in S and v is adjacent to no other vertex in S, or v is not in S but is adjacent to precisely one vertex of S. A graph G may have none, one or more than one perfect dominating sets. The problem of determining if a graph has a perfect dominating set is NP-complete. The problem of calculating the probability of an arbitrary graph having a perfect dominating set seems also difficult. In 1994 Yue [1] conjectured that almost all graphs do not have a perfect dominating set. In this paper, by introducing multiple interrelated generating functions and using combinatorial computation techniques we calculated the number of perfect dominating sets among all trees (rooted and unrooted) of order n for each n up to 500. Then we calculated the average number of perfect dominating sets per tree (rooted and unrooted) of order n for each n up to 500. Our computational results show that this average number is approaching zero as n goes to infinity thus suggesting that Yue’s conjecture is true for trees (rooted and unrooted).

A Sufficient Condition for 2-Distance-Dominating Cycles

A cycle C of a graph G is a m-distance-dominating cycle if for all vertices of . Defining denotes the minimum value of the degree sum of any k independent vertices of G. In this paper, we prove that if G is a 3-connected graph on n vertices, and if , then every longest cycle is m-distance-dominating cycles.

Dominating Sets and Domination Polynomials of Square of Paths

Let G = (V, E) be a simple graph. A set S í V is a dominating set of G, if every vertex in V-S is adjacent to at least one vertex in S. Let be the square of the Path and let denote the family of all dominating sets of with cardinality i. Let . In this paper, we obtain a recursive formula for . Using this recursive formula, we construct the polynomial, , which we call domination polynomial of and obtain some properties of this polynomial.

Construction of an Energy-Efficient Detour Non-Split Dominating Set in WSN

Wireless sensor networks(WSNs)are one of the most important improvements due to their remarkable capacities and their continuous growth in various applications.However,the lifetime of WSNs is very confined because of the delimited energy limit of their sensor nodes.This is the reason why energy conservation is considered the main exploration worry for WSNs.For this energy-efficient routing is required to save energy and to subsequently drag out the lifetime of WSNs.In this report we use the Ant Colony Optimization(ACO)method and are evaluated using the Genetic Algorithm(GA),based on the Detour non-split dominant set(GA)In this research,we use the energy efficiency returnee non-split dominating set(DNSDS).A set S⊆V is supposed to be a DNSDS of G when the graph G=(V,E)is expressed as both detours as well as a non-split dominating set of G.Let the detour non-split domination number be addressed asγ_dns(G)and is the minimum order of its detour non-split dominating set.Any DNSDS of orderγdns(G)is aγdns-set of G.Here,theγ_dns(G)of various standard graphs is resolved and some of its general properties are contemplated.A connected graph usually has an order n with detour non-split domination number as n or n–1 are characterized.Also connected graphs of order n≥4 and detour diameter D≤4 with detour non-split dominating number n or n−1 or n−2 are additionally portrayed.While considering any pair of positive integers to be specific a and b,there exists a connected graph G which is normally indicated as dn(G)=a,γ(G)=b andγdns(G)=a+b−2,hereγdns(G)indicates the detour domination number and dn(G)indicates the detour number of a graph.The time is taken for the construction and the size of DNSDS are considered for examining the performance of the proposed method.The simulation result confirms that the DNSDS nodes are energy efficient.

The Number of Minimum Roman and Minimum Total Dominating Sets for Some Chessboard Graphs

In this paper, both the roman domination number and the number of minimum roman dominating sets are found for any rectangular rook’s graph. In a similar fashion, the roman domination number and the number of minimum roman dominating sets are found on the square bishop’s graph for odd board sizes. Also found are the number of minimum total dominating sets associated with the light-colored squares when n?≡1(mod12)? (with n>1), and same for the dark-colored squares when n?≡7(mod12) .

An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem

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.

A two-level meta-heuristic approach for the minimum dominating tree problem

1 Introduction The minimum dominating tree(MDT)problem was first proposed by Zhang et al.[1]to produce a routing backbone of a WSN.Shin et al.[2]proved that the MDT problem is NP-hard and introduced an approximation framework for solving it.Recent important MDT problem algorithms are the artificial bee colony(ABC_DT)algorithm and ant colony optimization(ACO_DT)algorithm proposed by Sundar and Singh[3],the evolutionary algorithm with guided mutation(EA/G-MP)proposed by Chaurasia and Singh[4],the variable neighborhood search algorithm proposed by Dražićet al.[5],one improved artificial bee colony(ABC_DTP)algorithm proposed by Singh and Sundar[6],and a hybrid algorithm combining genetic algorithm proposed by Hu et al.[7].In this paper,we develop a two-level meta-heuristic(TLMH)for solving the MDT problem,aiming to find a dominating tree with the minimum weight for a given graph.