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.

(α,β)-constraints connected dominating set algorithm in wireless sensor network

To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set （CDS） algorithm with （α,β）-constraints is proposed. Based on the （α, β）-tree concept, a new connected dominating tree with bounded transmission delay problem（CDTT） is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes. The CDT algorithm consists of two phases： The first phase constructs a maximum independent set（MIS）in a unit disk graph model. The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPF, respectively. The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTF problem and forms a virtual backbone with（ α,β）-constraints balancing the requirements of power consumption and transmission delay.

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].

Area-Based Connected Dominating Set Construction and Maintenance Algorithm in Ubiquitous Stub Environment

In order to construct and maintain stability Connected Dominating Set over MANET in Ubiquitous Stub Network, this paper proposes a novel area-based CDS construction and maintenance algorithm. The algorithm is divided into three phases: 1) Area Partition; 2) Area Expansion; 3) Area Connection. In additional, maintenance strategy is proposed in each phase respectively to handle node mobility with timer. At last, the simulation is implemented with OPNET and MATLAB and the results are analyzed in detailed with Size of CDS, Message Overhead and other indexes.

An effective connected dominating set based mobility management algorithm in MANETs

This paper proposes a connected dominating set (CDS) based mobility management algorithm, CMMA, to solve the problems of node entering, exiting and movement in mobile ad hoc networks (MANETs), which ensures the connectivity and efficiency of the CDS. Compared with Wu's algorithm, the proposed algorithm can make full use of present network conditions and involves fewer nodes. Also it has better performance with regard to the approximation factor, message complexity, and time complexity.

Calculation of Minimal Dominating Set in Wireless Sensor Network with Host Switch-on/off

This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Considering that the hosts in mobile networks have different characteristics, this paper proposes a method of calculating minimal dominating set with weight. The nodes can be chosen to form a minimal dominating set when the network topology changes. For the host switch on/off operation, the updating algorithm was provided. The change in the status of a hostaffects only the status of hosts in the restricted vicinity. Simulation results show that the proposed method can ensure fewer dominators but with higher weight to form the minimal dominating set and the nodes can be adaptive to the changes of network topology.

AN EFFICIENT DISTRIBUTED ALGORITHM FOR CONNECTED DOMINATING SET CONSTRUCTION IN WIRELESS SENSOR NETWORKS

Efficient broadcasting protocols based on Connected Dominating Set (CDS) are frequently used;hence the entire broadcast domain is restricted to nodes in the CDS. This letter proves that a node must be a CDS node, if its neighbors with larger keys cannot cover it together.Then a simple distributed CDS construction algorithm is proposed, which is more effective than the existing algorithms in reducing the dominating set size and the computation complexity at the same time. Simulation results also confirm this, especially in relatively dense networks.

A Distributed Virtual Backbone Formation for Wireless Ad Hoc and Sensor Networks

The virtual backbone is an approach for solving routing problems in wireless ad hoc and sensor networks. A connected dominating set (CDS) was proposed as a virtual backbone to improve the performance of wireless networks. The quality of a virtual backbone is measured not only by approximation factor, which is the ratio of its size to that of minimum CDS, but also time complexity and message complexity. In this paper, a distributed algorithm is presented to construct a minimum CDS for ad hoc and sensor networks. By destroying triangular loops in the virtual backbone, the proposed algorithm can effectively construct a CDS with smaller size. Moreover, our algorithm, which is fully localized, has a constant approximation ratio, linear message and time complexity, and low implementation complexity. The simulation results and theoretical analysis show that our algorithm has better efficiency and performance than conventional approaches.

Twin domination in generalized Kautz digraphs

Let G = （V,A） be a digraph.A set T of vertices of G is a twin dominating set of G if for every vertex v ∈ V ／ T.There exist u,w ∈ T （possibly u = w） such that （u,v）,（v,w） ∈ A.The twin domination number γ＊（G） of G is the cardinality of a minimum twin dominating set of G.In this paper we consider the twin domination number in generalized Kautz digraphs GK（n,d）.In these digraphs,we establish bounds on the twin domination number and give a sufficient condition for the twin domination number attaining the lower bound.We give the exact values of the twin domination numbers by constructing minimum twin dominating sets for some special generalized Kautz digraphs.

Backbone formulation algorithm in wireless sensor network based on cross-entropy method

In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected dominating set in an arbitrary graph.In this paper,based on cross-entropy method,we present a novel backbone formulation algorithm(BFA-CE)in wireless sensor network.In BFA-CE,a maximal independent set is got at first and nodes in the independent set are required to get their action sets.Based on those action sets,a backbone is generated with the cross-entropy method.Simulation results show that our algorithm can effectively reduce the size of backbone network within a reasonable message overhead,and it has lower average node degree.This approach can be potentially used in designing efficient broadcasting strategy or working as a backup routing of wireless sensor network.

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.

Paired, Total, and Connected Domination on the Queen’s Graph Revisited

The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that every square of an n × n board is attacked? Beginning in 2005 with Amirabadi, Burchett, and Hedetniemi [2] [3], work on this problem, and two other related problems, has seen progress. Bounds have been given for the values of all three domination parameters on the queen’s graph. In this paper, formations of queens are given that provide new bounds for the values of total, paired, and connected domination on the queen’s graph, denoted , , and respectively. For any n × n board size, the new bound of is arrived at, along with the separate bounds of , for with , and , for with .

On Total Domination Polynomials of Certain Graphs

We have introduced the total domination polynomial for any simple non isolated graph G in [7] and is defined by Dt（G, x） = ∑in=yt（G） dr（G, i） x＇, where dr（G, i） is the cardinality of total dominating sets of G of size i, and yt（G） is the total domination number of G. In [7] We have obtained some properties of Dt（G, x） and its coefficients. Also, we have calculated the total domination polynomials of complete graph, complete bipartite graph, join of two graphs and a graph consisting of disjoint components. In this paper, we presented for any two isomorphic graphs the total domination polynomials are same, but the converse is not true. Also, we proved that for any n vertex transitive graph of order n and for any v ∈ V（G）, dt（G, i） = 7 dt（V）（G, i）, 1 〈 i 〈 n. And, for any k-regular graph of order n, dr（G, i） = （7）, i 〉 n-k and d,（G, n-k） = （kn） - n. We have calculated the total domination polynomial of Petersen graph D,（P, x） = 10X4 ＋ 72x5 ＋ 140x6 ＋ 110x7 ＋ 45x8 ＋ [ 0x9 ＋ x10. Also, for any two vertices u and v of a k-regular graph Hwith N（u） ≠ N（v） and if Dr（G, x） = Dt（ H, x ）, then G is also a k-regular graph.

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Abstract Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In this paper, authors consider a machine scheduling problem with controllable processing times. In the first part of this paper, a special case where the processing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O(n 2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case. An effective heuristic to the general problem will be presented.

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS ： PROOF OF THEOREMS

Abstract This report is virtually the appendix part of the author's previous paper which includes the proofs for the theorems and lemmas.

SOME RESULTS ON DOMINATION NUMBER OF PRODUCTS OF GRAPHS

Let G=(V,E) be a simple graph. A subset D of V is called a dominating set of G if for every vertex x∈V-D,x is adjacent to at least one vertex of D . Let γ(G) and γ c(G) denote the domination and connected domination number of G , respectively. In 1965,Vizing conjectured that if G×H is the Cartesian product of G and H , thenγ(G×H)≥γ(G)·γ(H).In this paper, it is showed that the conjecture holds if γ(H) ≠ γ c(H) .And for paths P m and P n , a lower bound and an upper bound for γ(P m×P n) are obtained.

A Distributed Design for Minimum 2-Connected m-Dominating Set in Bidirectional Wireless Ad-Hoc Networks

Wireless ad-hoc network is widely used in many fields for its convenience and outstanding suitability. Because of the inherent lack of infrastructure and the nature of wireless channels, people select the k-Connected m-Dominating Set （（k,m）-CDS） in a network as a fault-tolerant virtual backbone to help the routing process, which will save the energy of non-dominators and improve the network performance significantly. Considering the economic cost and efficiency, we choose （2,m）-CDS as the object of this paper, which is helpful enough in practical applications and has a smaller size. We firstly study the existing algorithms for （k,m）- CDS and figure out the problems of these designs. Then we propose a new distributed algorithm named Dominating Set Based AIgorithm （DSBA） with three sub-routines： Dominating Set AIgorithm （DSA）, Connection Algorithm （CA）, and Connectivity Expansion Algorithm （CEA）. Instead of commonly used Maximal Independent Set （MIS）, we pick dominating set directly from the given graph, and then connect them by a two-step ring based connecting strategy to satisfy the 2-connectivity. We also provide the correctness and complexity analysis of DSBA. At last, we compare DSBA with the last construction Distributed Deterministic Algorithm （DDA） by several numerical experiments. The simulation results show that DSBA improves over 30 percent of the performance of DDA, proving that DSBA is more practical for real-world applications.

Directed Dominating Set Problem Studied by Cavity Method:Warning Propagation and Population Dynamics

The minimal dominating set for a digraph(directed graph) is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution for a given graph that gives very good estimate of the minimal dominating size, we further developed the one step replica symmetry breaking theory to determine the ground state energy of the undirected minimal dominating set problem. The solution space for the undirected minimal dominating set problem exhibits both condensation transition and cluster transition on regular random graphs. We also developed the zero temperature survey propagation algorithm on undirected Erds-Rnyi graphs to find the ground state energy. In this paper we continue to develope the one step replica symmetry breaking theory to find the ground state energy for the directed minimal dominating set problem. We find the following.(i) The warning propagation equation can not converge when the connectivity is greater than the core percolation threshold value of 3.704. Positive edges have two types warning, but the negative edges have one.(ii) We determine the ground state energy and the transition point of the Erd?os-R′enyi random graph.(iii) The survey propagation decimation algorithm has good results comparable with the belief propagation decimation algorithm.

A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem

The minimum weight dominating set problem （MWDSP） is an NP-hard problem with a lot of real-world applications. Several heuristic algorithms have been presented to produce good quality solutions. However, the solution time of them grows very quickly as the size of the instance increases. In this paper, we propose a binary particle swarm optimization （FBPSO） for solving the MWDSP approximately. Based on the characteristic of MWDSP, this approach designs a new position updating rule to guide the search to a promising area. An iterated greedy tabu search is used to enhance the solution quality quickly. In addition, several stochastic strategies are employed to diversify the search and prevent premature convergence. These methods maintain a good balance between the exploration and the exploitation. Experimental studies on 106 groups of 1 060 instances show that FBPSO is able to identify near optimal solutions in a short running time. The average deviation between the solutions obtained by FBPSO and the best known solutions is 0.441%. Moreover, the average solution time of FBPSO is much less than that of other existing algorithms. In particular, with the increasing of instance size, the solution time of FBPSO grows much more slowly than that of other existing algorithms.