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"”.

  1. 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 …

    unlv Repository record for Generating quality dominating set (opens in a new tab) Download PDF for Generating quality dominating set (opens in a new tab)

  2. 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. …

    concordia Download PDF for In solving the dominating set problem : group theory approach (opens in a new tab)

  3. 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 …

    ottawa-retro Repository record for Energy efficient dominating set based topology maintenance in ad hoc wireless networks (opens in a new tab)

  4. 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 …

    waterloo Repository record for On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set (opens in a new tab)

  5. 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 …

    ubc Repository record for Design and analysis of a connected dominating set algorithm for mobile ad hoc networks (opens in a new tab) Download PDF for Design and analysis of a connected dominating set algorithm for mobile ad hoc networks (opens in a new tab)

  6. 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 …

    lethbridge Repository record for Integer programming formulation for contention aware connected dominating set in wireless multi-hop network (opens in a new tab)

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

    clemson Repository record for A LOAD-BASED APPROACH TO FORMING A CONNECTED DOMINATING SET FOR AN AD HOC NETWORK (opens in a new tab)

  8. 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 …

    arizona-thes Repository record for Novel Integer Optimization Methods and their Applications in Biomass Supply Chain and Power Dominating Set (opens in a new tab)

  9. 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 …

    vcu Repository record for Parity Domination in Product Graphs (opens in a new tab)

  10. 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. …

    jhu Repository record for EFFICIENT AND PERFECT DOMINATION ON ARCHIMEDEAN LATTICES (opens in a new tab)

  11. 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 …

    usf Repository record for Connected Domination in Graphs (opens in a new tab)

  12. 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 …

    etsu Repository record for Very Cost Effective Domination in Graphs (opens in a new tab) Download PDF for Very Cost Effective Domination in Graphs (opens in a new tab)

  13. 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 …

    etsu Repository record for Paired-Domination in Grid Graphs. (opens in a new tab) Download PDF for Paired-Domination in Grid Graphs. (opens in a new tab)

  14. 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 …

    etsu Repository record for Global Domination Stable Graphs (opens in a new tab) Download PDF for Global Domination Stable Graphs (opens in a new tab)

  15. 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 …

    etsu Repository record for Cost Effective Domination in Graphs (opens in a new tab) Download PDF for Cost Effective Domination in Graphs (opens in a new tab)

  16. 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 …

    waterloo Repository record for On Two Combinatorial Optimization Problems in Graphs: Grid Domination and Robustness (opens in a new tab)

  17. 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 …

    jhu Repository record for Total Domination Ratios of Archimedean Lattices (opens in a new tab)

  18. 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 …

    etsu Repository record for Placing Monitoring Devices in Electric Power Networks Modeled by Block Graphs. (opens in a new tab) Download PDF for Placing Monitoring Devices in Electric Power Networks Modeled by Block Graphs. (opens in a new tab)

  19. 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 …

    clemson Repository record for Fault Tolerance in Distributed Systems Using Self-Stabilization (opens in a new tab)

Page 1 of 6