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.

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.

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.

Edge-Vertex Dominating Sets and Edge-Vertex Domination Polynomials of Cycles

Let G = (V, E) be a simple graph. A set S E(G) is an edge-vertex dominating set of G (or simply an ev-dominating set), if for all vertices v V(G);there exists an edge eS such that e dominates v. Let denote the family of all ev-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 edge-vertex domination polynomial of (or simply an ev-domination polynomial of ) and obtain some properties of this polynomial.

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.

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.

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.

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.

Almost Stochastic Dominance and Efficient Investment Sets

A major drawback of Mean-Variance and Stochastic Dominance investment criteria is that they may fail to determine dominance even in situations when all “reasonable” decision-makers would clearly prefer one alternative over another. Leshno and Levy [1] suggest Almost Stochastic Dominance (ASD) as a remedy. This paper develops algorithms for deriving the ASD efficient sets. Empirical application reveals that the improvement to the efficient sets implied by ASD is substantial (64% reduction for FSD). Direct expected utility maximization shows that investment portfolios excluded from the ASD efficient set would not have been chosen by any investors with reasonable preferences.

Multi-hierarchical fuzzy judgment and nested dominance relation of rough set theory-based environmental risk evaluation for tailings reservoirs

Environmental risk assessment of tailings reservoir assessment system is complex and has many index factors.In order to accurately judge surrounding environmental risks of tailings reservoirs and determinate the corresponding prevention and control work,multi-hierarchical fuzzy judgment and nested dominance relation of rough set theory are implemented to evaluate them and find out the rules of this evaluation system with 14 representative cases.The methods of multi-hierarchical fuzzy evaluation can overall consider each influence factor of risk assessment system and their mutual impact,and the index weight based on the analytic hierarchy process is relatively reasonable.Rough set theory based on dominance relation reduces each index attribute from the top down,largely simplifies the complexity of the original evaluation system,and considers the preferential information in each index.Furthermore,grey correlation theory is applied to analysis of importance of each reducted condition attribute.The results demonstrate the feasibility of the proposed safety evaluation system and the application potential.

Rock burst laws in deep mines based on combined model of membership function and dominance-based rough set

Rock bursts are spontaneous, violent fracture of rock that can occur in deep mines, and the likelihood of rock bursts occurring increases as depth of the mine increases. Rock bursts are also affected by the compressive strength, tensile strength, tangential strength, elastic energy index, etc. of rock, and the relationship between these factors and rock bursts in deep mines is difficult to analyze from quantitative point. Typical rock burst instances as a sample set were collected, and membership function was introduced to process the discrete values of these factors with the discrete factors as condition attributes and rock burst situations as decision attributes. Dominance-based rough set theory was used to generate preference rules of rock burst, and eventually rock burst laws analysis in deep mines with preference relation was taken. The results show that this model for rock burst laws analysis in deep mines is more reasonable and feasible, and the prediction results are more scientific.

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

Interactive multiobjective optimization using dominance-based rough set approach

We present main ideas of a recently proposed method for interactive multiobjective optimization,which is based on application of a logical preference model built using the Dominance-based Rough Set Approach(DRSA).

Dominance-based rough set approach as a paradigm of knowledge discovery and granular computing

Dominance-based rough set approach(DRSA) permits representation and analysis of all phenomena involving monotonicity relationship between some measures or perceptions.DRSA has also some merits within granular computing,as it extends the paradigm of granular computing to ordered data,specifies a syntax and modality of information granules which are appropriate for dealing with ordered data,and enables computing with words and reasoning about ordered data.Granular computing with ordered data is a very general paradigm,because other modalities of information constraints,such as veristic,possibilistic and probabilistic modalities,have also to deal with ordered value sets(with qualifiers relative to grades of truth,possibility and probability),which gives DRSA a large area of applications.

Dominance-Based Rough Set Approach in Selection of Portfolio of Sustainable Development Projects

In our study, the Dominance-based Rough Set Approach (DRSA) has been proposed to assist the Board of Directors of the Community Futures Development Corporations (CFDC), the sub-region of Abitibi-West (Quebec). The CFDC needs a tool for decision support to select the projects that are proposed by the contractors and partners of its territory. In decision making, a balanced set of 22 indicators is considered. These indicators derive from five perspectives: economic, social, demographic, health and wellness. The DRSA proposal is suitable for the data processing with multiple indicators providing on many examples to infer decision rules related to the preference model. In this paper we show that decision rules developed with the use of rough set theory allow us to simplify the process of selecting a portfolio for sustainable development by reducing a number of redundant indicators and identifying the critical values of selected indicators.

基于邻域优势粗糙集的区分度动态属性约简算法

为解决动态环境下数值型偏序关系数据的属性约简问题,利用优势粗糙集的区分度提出一种增量式属性约简算法。在数值型信息系统环境下,定义邻域优势区分度度量,通过邻域优势区分度设出一种非增量式属性约简算法;研究和分析对象变化场景下邻域优势区分度进行增量式更新的原理;分别提出数据对象增加和减少情形下数据集属性约简的增量式更新算法。在多个UCI数据集上进行实验验证,实验结果表明,该增量式算法能够有效完成动态数据的属性约简任务。

无爪图的支撑k-端点树的存在性

树T中度为1的点称为叶子,叶子数目不超过k的树称为k-端点树.图中存在一个哈密尔顿路,说明图中存在恰好含有两个叶子的支撑树.自然就有了关于哈密尔顿路问题的一个推广:考虑图中至多有k个叶子的支撑树即支撑k-端点树的存在性问题.通过控制集参数,确定了连通无爪图中存在支撑k-端点树条件.