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 11 of 11 for “"Maximal independent set"”.
-
Well-covered Graphs, Unique Colorability, and Covering Range
<p>A graph is called well-covered if all of its maximal independent sets have the same cardinality. We give a characterization of well-covered k-trees. A graph is said to be uniquely χ-colorable if, modulo permutations of colors, it has exactly one proper χ-coloring. The k-trees with at least k+1 …
-
Efficient Computation of Extremal Structures in Graphs and Hypergraphs
An independence system consists of a ground set and a collection of subsets of the ground set called independent sets with the property that any subset of an independent set is independent. We study the problem of computing a maximal independent set (mis) in an independence system. We propose two …
-
Tournament based task allocation in a parallel MIS algorithm
… allocation and dependency tracking in a parallel Maximal Independent Set (MIS) algorithm as a way to reduce contention in counter updates and improve runtime. The tournament data structure adds a noticeable overhead to the algorithm that causes T time of the algorithm to increase but then there is …
-
Improved distributed algorithms for fundamental graph problems
… 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 …
-
New directions in sublinear algorithms and testing properties of distributions
… to the conditional distribution on a specified set, allows one to get faster algorithms for a number of problems. Thirdly, this thesis considers the problem of certifying and correcting the result of a crowdsourced computation with potentially erroneous worker reports, by using verification …
-
A Parallel Aggregation Algorithm for Inter-Grid Transfer Operators in Algebraic Multigrid
As finite element discretizations ever grow in size to address real-world problems, there is an increasing need for fast algorithms. Nowadays there are many GPU/CPU parallel approaches to solve such problems. Multigrid methods can be used to solve large-scale problems, or even better they can be …
-
A constructive lower bound for cardinality of codebooks capable of correcting multiple deletion and insertions
… the largest codebook can be converted into an independent set problem in some specific graphs. The exact solution for the maximal independent set in these graphs is equivalent to finding the largest possible codebooks capable of correcting specific number of deletions and insertions. We propose …
-
Relaxed concurrent ordering structures
… which are easy to support in sequential settings are stronger than necessary for concurrent applications, and instead define new semantics for implementing relaxed ordering structures: relaxed structures need only return elements which are probabilistically near the head element. This …
-
New methods for branch-and-bound algorithms
… These algorithms are used in a wide variety of settings, and thus it is beneficial to develop new techniques to improve the performance of B&B algorithms that are independent of the specific problem being studied. This dissertation describes three such techniques. First, new results for the …
-
SOLVING PROCESS PLANNING AND SCHEDULING PROBLEMS USING THE CONCEPT OF MAXIMUM WEIGHTED INDEPENDENT SET
… at each time slot. Then, the Maximum Weighted Independent Set (MWIS) problem, which considers a graph with weights assigned to nodes and seeks to discover the “heaviest” independent set, that is, a set of nodes with maximum total weight so that no two nodes in the set are connected by an edge, …
-
Constant time algorithms in sparse graph model
… Matching, Maximum Weighted Matching, Maximum Independent Set and Set Cover. Some of our techniques can also be applied to design constant-time testers for minor-closed properties. In Chapter 1, we show how to construct a simple oracle that provides query access to a fixed Maximal Independent …