NDLTD logo NDLTD Union Catalog and Global ETD Search

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 40 for “"dominating set"”.

  1. In solving the dominating set problem : group theory approach

    Ma, Ka Leung1998

    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 Repository record

  2. Integer programming formulation for contention aware connected dominating set in wireless multi-hop network

    Nawrin Ferdous, Chowdhury, University of Lethbridge. Faculty of Arts and ScienceLethbridge, Alta. : Universtiy of Lethbridge, Department of Mathematics and Computer Science2020

    … 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

  3. Novel Integer Optimization Methods and their Applications in Biomass Supply Chain and Power Dominating Set

    Sun, OuThe University of Arizona.2019

    … 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

  4. The bidimensionality theory and its algorithmic applications

    Hajiaghayi, MohammadTaghiMassachusetts Institute of Technology2005

    … of such problems include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex- removal parameters, dominating set, edge dominating set, r-dominating set, connected dominating set, connected edge dominating set, connected r-dominating set, and …

    mit Repository record

  5. Global Domination Stable Graphs

    Harris, Elizabeth Marie2012

    <p>A set of vertices <i>S</i> in a graph <i>G</i> is a global dominating set (GDS) of <i>G</i> if <i>S</i> is a dominating set for both <i>G</i> and its complement <i>G</i>. The minimum cardinality of a global dominating set of <i>G</i> is the global domination number of <i>G</i>. We explore the …

    etsu Repository record

  6. Cost Effective Domination in Graphs

    McCoy, Tabitha Lynn2012

    <p>A set <em>S</em> of vertices in a graph <em>G</em> = (<em>V</em>,<em>E</em>) is a dominating set if every vertex in <em>V</em> \ <em>S</em> is adjacent to at least one vertex in <em>S</em>. A vertex <em>v</em> in a dominating set <em>S</em> is said to be it <em>cost effective</em> if it is …

    etsu Repository record

  7. Placing Monitoring Devices in Electric Power Networks Modeled by Block Graphs.

    Atkins, David Wayne2003

    … related to the well known vertex covering and dominating set problems in graph theory. A set <em>S</em> 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 <em>S</em> (following a set of rules for power system …

    etsu Repository record

  8. Paired-Domination in Grid Graphs.

    Proffitt, Kenneth Eugene2001

    … <em>G</em> = (<em>V</em>, <em>E</em>) has a dominating set <em>S</em> ⊆ <em>V</em>(<em>G</em>) such that any vertex not in <em>S</em> is adjacent to a vertex in <em>S</em>. We define a paired-dominating set <em>S</em> to be a dominating set <em>S</em> = {<em>v</em><sub>1</sub>, …

    etsu Repository record

  9. Domination in Sparse Graphs

    Stodolsky, Burak YildiranUniversity of Illinois at Urbana-Champaign2015

    … of V (G) with parts ( V1, V2, ... , V t). A pi-dominating set B is a dominating set that is the union of parts of pi. The pi-domination number gamma(G,pi) of G is the size of a smallest pi-dominating set. If each Vi in pi has size at most 2, we call pi a coupling of G and say that the vertices …

    uiuc Repository record

  10. Locating and Total Dominating Sets in Trees.

    Howard, Jamie Marie2004

    <p>A set <em>S</em> of vertices in a graph <em>G</em>=(<em>V</em>,<em>E</em>) is a total dominating set of <em>G</em> if every vertex of <em>V</em> is adjacent to some vertex in <em>S</em>. In this thesis, we consider total dominating sets of minimum cardinality which have the additional property …

    etsu Repository record

  11. Liar's Domination in Grid Graphs

    Sterling, Christopher Kent2012

    … in N[<em>v</em>] the intruder is located. A dominating set is required to identify any intruder's location in the graph <em>G</em>, and if any one device can fail to detect the intruder, then a double-dominating set is necessary. Stronger still, a liar's dominating set can identify an …

    etsu Repository record

  12. Double Domination of Complementary Prisms.

    Vaughan, Lamont D2008

    … and <em>G̅</em>. For any graph <em>G</em>, a set <em>D</em> ⊆ <em>V</em> (<em>G</em>) is a <em>double dominating set</em> (DDS) if that set dominates every vertex of <em>G</em> twice. The <em>double domination number</em>, denoted γ<sub>×2</sub>(<em>G</em>), is the cardinality of a minimum …

    etsu Repository record

  13. Multiple domination in graphs

    Hansberg Pastor, AdrianaPublikationsserver der RWTH Aachen University2009

    … an undirected and simple graph G = (V , E), a subset D of the vertex set is called a k-dominating set if every vertex not in D has at least k neighbors in D. This concept was introduced by Fink and Jacobson in the year 1985, generalizing the already much studied concept of domination in graphs. In …

    aachen Repository record

  14. Explorations in the Classification of Vertices as Good or Bad.

    Jackson, Eugenie Marie2001

    <p>For a graph <em>G</em>, a set <em>S</em> is a dominating set if every vertex in <em>V</em>-<em>S</em> has a neighbor in <em>S</em>. A vertex contained in some minimum dominating set is called good; otherwise it is bad. A graph <em>G</em> has <em>g</em>(<em>G</em>) good vertices and …

    etsu Repository record

  15. Locating-Domination in Complementary Prisms.

    Holmes, Kristin Renee Stone2009

    … vertices of <em>G</em> and <em>G̅</em>. A set <em>D</em> ⊆ <em>V</em> (<em>G</em>) is a locating-dominating set of <em>G</em> if for every <em>u</em> ∈ <em>V</em> (<em>G</em>)<em>D</em>, its neighborhood <em>N</em>(<em>u</em>)⋂<em>D</em> is nonempty and distinct from …

    etsu Repository record

  16. Degree Ramsey theory, game and Roman domination, and game saturation in graphs

    Kinnersley, WilliamUniversity of Illinois at Urbana-Champaign2012

    … w in a graph if w is adjacent or equal to v; a dominating set is a set that dominates all vertices. In this game, two players jointly construct a dominating set S in a graph G by alternately adding vertices; each addition must strictly increase the number of vertices dominated. One player aims …

    uiuc Repository record

  17. Adaptive clustering and transmission range adjustment for topology control in wireless sensor networks

    Yin, BolianUniversity of Missouri--Columbia2006

    … to achieve further energy saving. Connected dominating set (CDS) as a very promising energy saving technique can be used with either a transmission-power-based algorithm or a dutycycle- based algorithm. I have designed a distributed algorithm, DSP-CDS, for constructing CDS quickly in a single …

    missouri Repository record

  18. Power Domination in graphs

    Reagon, DeanDepartment of Mathematics and Applied Mathematics2025

    … essentially the number of steps it takes a power dominating set of vertices to monitor a graph. We show how ideas from domina-tion can be extended to power domination and k-power domination. We show how domination differs from k-power domination. We demonstrate how making small changes to a graph …

    cape-town Repository record

  19. Energy-Aware Topology Control and Data Delivery in Wireless Sensor Networks

    Park, Seung-JongGeorgia Institute of Technology2004

    … 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 robustness, …

    gatech Repository record

  20. Improved distributed algorithms for fundamental graph problems

    Ghaffari, MohsenMassachusetts Institute of Technology2017

    … for solving graph problems in distributed settings and more generally for performing distributed computation in networks. These algorithms are applicable in a wide variety of settings, ranging from computer networks to massively parallel computing and beyond. This thesis addresses a number …

    mit Repository record

Page 1 of 2