Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 16 of 16 for “"Minimum dominating set"”.
-
A graph theory approach of the study of macroeconomics networks
… in the context of Network Analysis is the Minimum Spanning Tree (MST). The MST produces a sub-graph of the initial network in which all the nodes are connected so that no loops exist. However, the MST bears some inherent drawbacks that stem directly from its algorithmic identification …
-
Efficient Algorithms for RDV graphs
In this thesis, we study the maximum matching and minimum dominating set problem in RDV graphs, i.e., graphs that are vertex-intersection graphs of downward paths in a rooted tree. A straightforward implementation of these algorithms would require $O(n+m)$ time. We improve their efficiency by …
-
Energy-Aware Topology Control and Data Delivery in Wireless Sensor Networks
… GARUDA-UP which share a common structure, the minimum dominating set. For the downstream data delivery, we consider reliability as well as energy conservation since unreliable data delivery can increase energy consumption under high data loss rates. To reduce energy consumption and achieve …
-
Domination in Benzenoids
… graph is a fragment of the hexagon lattice. A dominating set $D$ in a graph $G$ is a set of vertices such that each vertex of the graph is either in $D$ or adjacent to a vertex in $D$. The domination number $\gamma=\gamma(G)$ of a graph $G$ is the size of a minimum dominating set. We will find …
-
Upset Paths and 2-Majority Tournaments
… arising from majority voting scenarios have minimum dominating sets that are bounded by a constant that depends only on the notion of what is meant by a majority. Moreover, they proved that when a majority means that Candidate A beats Candidate B when Candidate A is ranked above Candidate B …
-
Explorations in the Classification of Vertices as Good or Bad.
For a graph G, a set S is a dominating set if every vertex in V-S has a neighbor in S. A vertex contained in some minimum dominating set is called good; otherwise it is bad. A graph G has g(G) good vertices and b(G) bad vertices. The relationship between the order of G and g(G) assigns the graph to …
-
A LINEAR-TIME ALGORITHM FOR BROADCAST DOMINATION IN A TREE
… domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power p at vertex v is capable of dominating all vertices within distance p from v. Our goal is to assign a broadcast power f(v) to every vertex v in a graph such that the sum for all v over V …
-
Computational methods for domination problems
For a graph G, the minimum dominating set problem is to find a minimum size set S of vertices of G such that every vertex is either in S or adjacent to a vertex in the set. The decision version of this problem, which asks whether G has a dominating set of a particular size k, is known to be …
-
Vertex-Criticality and Bicriticality for Independent Domination and Total Domination in Graphs
… gamma-graph of G is the graph where the vertex set is the collection of minimum dominating sets of G. Adjacency between two minimum dominating sets in the gamma-graph occurs if from one minimum dominating set a vertex can be removed and replaced with a vertex to arrive at the other minimum …
-
Efficient Network Domination for Life Science Applications
… to match problems being studied. Often only a subset of variables may be utilized or studied further, motivating the need of techniques that can prioritize variable selection. This dissertation describes the development and application of graph theoretic techniques, particularly the notion of …
-
Sampling combinatorial energy landscapes by classical and quantum computation
… inequivalent regions, iii) solution of the minimum dominating set variant of the optimal phasor measurement unit placement problem on the power grid by quantum-annealing over a discrete, combinatorial solution landscape, iv) a reformulation and solution of the Markov decision process …
-
Energy efficient clustering and secure data aggregation in wireless sensor networks
… distributed. We introduce the energy constrained minimum dominating set (ECDS) to model the problem of optimally choosing cluster heads in the presence of energy constraints. We show its applicability to sensor networks and give an approximation algorithm of O(log n) for solving the ECDS problem. …
-
Algorithms for NP-hard Optimization Problems and Cluster Analysis
The set cover problem, weighted set cover problem, minimum dominating set problem and minimum weighted dominating set problem are all classical NP-hard optimization problems of great importance in both theory and real applications. Since the exact algorithms, which require exhaustive exploration of …
-
The power of frequency hopping and information dissemination in constrained communication models
… problems we study are leader election, wake-up, minimum dominating set, maximal independent set and connected dominating set. If we denote with n the size of the network and with F the number of communication channels, then for all the above mentioned problems we can show a speed-gain roughly in …
-
Generic Architecture for Power-Aware Routing in Wireless Sensor Networks
… better when the transmission range is kept to a minimum for network connectivity as compared to adjustable transmission range.
-
Flexible integration of classical and quantum techniques in the evolutionary path to quantum utility
… classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded …