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 20 for “"Dominating Set Problem"”.
-
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. …
-
On Two Combinatorial Optimization Problems in Graphs: Grid Domination and Robustness
In this thesis, we study 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. …
-
Dominating sets in Kneser graphs
This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures. We begin with background on the …
-
Efficient Algorithms for RDV graphs
… 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 transforming …
-
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 …
-
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 …
-
Integer Programming Techniques for Propagation and Rainbow Connection Problems in Graphs
… a collection of combinatorial optimization problems and the integer programs proposed to solve them based on new mathematical insights. In particular, graph propagation and graph throttling problems including the positive semidefinite zero forcing set problem and the minimum power dominating …
-
A LINEAR-TIME ALGORITHM FOR BROADCAST DOMINATION IN A TREE
The broadcast 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 …
-
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 …
-
Robust and Survivable Network Design Considering Uncertain Node and Link Failures
… of our research topic on network design problems. Different from literature on network design, we consider both uncertain node and link failures during the network design process. The first part of our research is to design a survivable network with mixed connectivity requirements, or the …
-
Adiabatic Quantum Computing with QUBO Formulations
… degrees) in a variety of classical computation problems. Several different models of quantum computing exist. Based on the Adiabatic Theorem in physics, Adiabatic Quantum Computing is a novel computing framework that is drastically different from the more traditional quantum logic gate model. …
-
Hardness results and approximation algorithms for some problems on graphs
… In the first part, we study some graph covering problems with a non-local covering rule that allows a "remote" node to be covered by repeatedly applying the covering rule. In the second part, we provide some results on the packing of Steiner trees. In the Propagation problem we are given a graph …
-
Broadcast in sparse conversion optical networks using fewest converters
… of available converters. The Converters Usage Problem (CUP) is to use a minimum number of converter so that each node can send messages to all the others (broadcasting). In this dissertation, we study the CUP in sparse conversion networks. We design a linear algorithm to find a wavelength …
-
Allocation Algorithms for Networks with Scarce Resources
… to computer networks. We consider several problems that crop up in wireless ad hoc networks, sensor networks, P2P networks, and cluster networks. The common challenge here is to deal with certain bottleneck resources that are crucial for performance of the underlying system. Broadly, we …
-
Generalized Domination in Graphs with Applications in Wireless Networks
… also considers wireless sensor placement problems with various additional constraints that reflect different real-life scenarios. In wireless ad-hoc network, a connected dominating set (CDS) can be used to serve as a virtual backbone, facilitating communication among the members in the …
-
Optimization in Geometric Graphs: Complexity and Approximation
We consider several related problems arising in geometric graphs. In particular, we investigate the computational complexity and approximability properties of several optimization problems in unit ball graphs and develop algorithms to find exact and approximate solutions. In addition, we establish …
-
Novel Integer Optimization Methods and their Applications in Biomass Supply Chain and Power Dominating Set
Integer optimization (IO) problems arise in research areas and our daily life almost in every aspect. IO formulations and methods can be adopted to make optimal decisions for solution-searching and management with global optimization. Two main areas of applications of IO are studied in the …
-
Domination : Offline, Online, Any Time
Given a graph G = (V, E), a subset D [is a subset of] V is called a dominating set if each vertex v [is a member of] V either belongs to D or is adjacent to some vertex in D. The typical objective is to find a dominating set of minimum size. Depending on the context, the problem may be viewed from …
-
Analyzing The Community Structure Of Web-like Networks: Models And Algorithms
… computational techniques: First, we consider the problem of modeling the web-like networks. In the recent years, many new random graph models have been proposed to account for some recently discovered properties of web-like networks that distinguish them from the classical random graphs. The vast …