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 20 of 115 for “"dominating set"”.
-
Generating quality dominating set
Construction of a small size dominating set is a well known problem in graph theory and sensor networks. A Connected dominating set (CDS) can be used as a backbone structure in sensor networks for message delivery and broadcast. The general dominating set problem is known to be NP-hard and some …
-
In solving the dominating set problem : group theory approach
This thesis presents a new way to find the dominating set of a graph by introducing the concept of an orbit graph and a weighted dominating set. We showed that the Blokhuis-Lam method for the football pool problem is a special case of assuming that the solution has a non-trivial automorphism group. …
-
Energy efficient dominating set based topology maintenance in ad hoc wireless networks
… are restricted to active nodes that create such dominating set. Activity status is periodically updated during a short transition period. The main contribution of this thesis is to propose new metrics for previously studied source independent localized dominating sets, based on combinations of …
-
On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set
A graph problem P is a vertex-subset problem if feasible solutions for P consist of subsets of the vertices of a graph G. The st-connectivity problem for a vertex-subset problem P takes as input two feasible solutions S_s and S_t, and determines if there is a sequence of recon figuration steps that …
-
Design and analysis of a connected dominating set algorithm for mobile ad hoc networks
Wireless technology such as IEEE 802.11b allows a set of devices to communicate with each other in a peer-to-peer manner by dynamically forming mobile ad hoc networks. Routing in such networks is challenging due to node mobility, low power, constrained bandwidth and limited radio range. Most of the …
-
Integer programming formulation for contention aware connected dominating set in wireless multi-hop network
… networks. Broadcasting with Minimum Connected Dominating Set (MCDS) is used to reduce redundant transmission. Contention occurs when a group of nodes want to transmit over a shared channel at the same time. During contention, nodes defer transmissions for a random time. Using Contention-aware …
-
A LOAD-BASED APPROACH TO FORMING A CONNECTED DOMINATING SET FOR AN AD HOC NETWORK
… (MANETs) is highly desired and connected dominating sets (CDS) have been gaining significant popularity in this regard. The CDS based approach reduces the search for a minimum cost path between a pair of source and destination terminals to the set of terminals forming the backbone network. …
-
Novel Integer Optimization Methods and their Applications in Biomass Supply Chain and Power Dominating Set
… of IO to power systems, especially power dominating set problems. The IO has been applied in almost every aspect of the power system industry, including power system network design problem, unit commitment problem, and sensor placement problem. Phasor Measurement Unit (PMU) placement …
-
Parity Domination in Product Graphs
An odd open dominating set of a graph is a subset of the graph’s vertices with the property that the open neighborhood of each vertex in the graph contains an odd number of vertices in the subset. An odd closed r-dominating set is a subset of the graph’s vertices with the property that the closed …
-
EFFICIENT AND PERFECT DOMINATION ON ARCHIMEDEAN LATTICES
… tiling of the plane by regular polygons. A set of vertices S is said to dominate a graph G=(V,E) if every vertex in V is either in the set S or is adjacent to a vertex in set S. A dominating set is a perfect dominating set if every vertex not in the dominating set is dominated exactly once. …
-
Connected Domination in Graphs
A connected dominating set D is a set of vertices of a graph G = (V, E) such that every vertex in V − D is adjacent to at least one vertex in D and the subgraph hDi induced by the set D is connected. The connected domination number γc(G) is the minimum of the cardinalities of the connected …
-
Very Cost Effective Domination in Graphs
A set S of vertices in a graph G=(V,E) is a dominating set if every vertex in V\S is adjacent to at least one vertex in S, and the minimum cardinality of a dominating set of G is the domination number of G. A vertex v in a dominating set S is said to be very cost effective if it is adjacent to more …
-
Paired-Domination in Grid Graphs.
Every graph G = (V, E) has a dominating set S ⊆ V(G) such that any vertex not in S is adjacent to a vertex in S. We define a paired-dominating set S to be a dominating set S = {v1, v2,..., v2t-1, v2t} where M = {v1v2, v3v4, ..., v2t-1v2t} is a perfect matching in 〈S〉, the subgraph induced by S. The …
-
Global Domination Stable Graphs
A set of vertices S in a graph G is a global dominating set (GDS) of G if S is a dominating set for both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications on the global domination …
-
Cost Effective Domination in Graphs
A set S of vertices in a graph G = (V,E) is a dominating set if every vertex in V \ S is adjacent to at least one vertex in S. A vertex v in a dominating set S is said to be it cost effective if it is adjacent to at least as many vertices in V \ S as it is in S. A dominating set S is cost effective …
-
On Two Combinatorial Optimization Problems in Graphs: Grid Domination and Robustness
… two problems in combinatorial optimization, the dominating set problem and the robustness problem. In the first half of the thesis, we focus on the dominating set problem in grid graphs and present a distributed algorithm for finding near optimal dominating sets on grids. The dominating set …
-
Total Domination Ratios of Archimedean Lattices
… regular tiling which is vertex transitive. A subset of vertices $D$ dominates a graph $G=(V_G,E_G)$ if all elements of $V_G$ either belong to $D$ or are adjacent to an element of $D$. A dominating set of vertices is a total dominating set if every vertex is adjacent to an element of the set. A …
-
Placing Monitoring Devices in Electric Power Networks Modeled by Block Graphs.
… related to the well known vertex covering and dominating set problems in graph theory. A set S of vertices is defined to be a power dominating set of a graphs if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The …
-
Fault Tolerance in Distributed Systems Using Self-Stabilization
… problems in distributed systems. Two variants of dominating set (i.e., weakly connected dominating set and positive influence dominating set) have been widely used in distributed system applications, such as network security, facility location, message routing and others. In this thesis, three new …
Page 1 of 6