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 25 for “"Independent set problem"”.
-
Algorithms for the Maximum Independent Set Problem
This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden …
-
On the maximum weighted independent set problem with applications in wireless sensor networks
The Maximum Weighted Independent Set (MWIS) Problem considers a graph with weights assigned to the nodes and seeks to discover the "heaviest" independent set, that is, a set of nodes with maximal total weight so that no two nodes in the set are connected by an edge. The MWIS problem arises in many …
-
A branch, price, and cut approach to solving the maximum weighted independent set problem
The maximum weight-independent set problem (MWISP) is one of the most well-known and well-studied NP-hard problems in the field of combinatorial optimization. In the first part of the dissertation, I explore efficient branch-and-price (B&P) approaches to solve MWISP exactly. B&P is a useful …
-
Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem
… (B&P) approach to solve the maximum weighted independent set problem (MWISP). Our approach uses clones of vertices to create edge-disjoint partitions from vertex-disjoint partitions. We solve the MWISP on sub-problems based on these edge-disjoint partitions using a B&P framework, which …
-
Approximation algorithms for independent set problems on hypergraphs
… with approximation algorithms for the Maximum Independent Set and the Minimum Hitting Set problems on hypergraphs. As a hypergraph is a generalization of a graph, the question is whether the best known approximations on graphs can be extended to hypergraphs. We consider greedy, local search and …
-
A SEMI-DEFINITE RELAXATION BRANCH-AND-BOUND ALGORITHM FOR BINARY INTEGER QUADRATIC PROBLEMS USING SCIPSUITE
The Binary Quadratic Optimization Problem is a classical problem and studied in many fields. Typical applications include the 0-1 Quadratic Problem (QP), the Maximum Cut Problem (MAXCUT), k-Cluster Problem (kCluster), Maximum Independent Set Problem (MIS) as well as the Exact k-Quadratic Knapsack …
-
Algoritmo relax-and-cut para o problema do conjunto independente máximo
… exact algorithms are proposed for the Maximum Independent Set Problem. Instead of the standard formulation of the problem, which usually leads to very weak linear relaxation bounds, we use a much stronger reformulation, based on an edge clique cover. The reformulation is new and is introduced …
-
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. …
-
Photonic quantum technologies: non-destructive photon detection and quantum simulation in solid-state systems
… applications like solving the maximum independent set problem. A very high fidelity exciton detection scheme was explored too.
-
A constructive lower bound for cardinality of codebooks capable of correcting multiple deletion and insertions
… number of deletions and insertions is an open problem in coding theory. The efforts in the design of these codes mostly concentrate on finding the largest codebook size for a fixed number of deletions and a codeword length. In fact, most of these codebooks are designed for a specific number of …
-
Efficient Algorithms on Cocomparability Graphs via Vertex Orderings
… characterizations and linear extensions of posets. To do so, we present new tools that we hope will prove useful on other applications – especially a new graph parti- tion refinement technique, and a new graph parameter that captures the linear structure exhibited by certain graph classes. The …
-
Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation
The rise of large-scale datasets across domains such as social networks, biological systems, and the web has made it increasingly important to understand how core graph problems can be solved under tight resource constraints. As these datasets grow, traditional algorithms that assume random access …
-
Novel approaches for solving large-scale optimization problems on graphs
… a class of closely related NP-hard otpimization problems on graphs that arise in many important applications, including network-based data mining, analysis of the stock market, social networks, coding theory, fault diagnosis, molecular biology, biochemistry and genomics. In particular, the …
-
Independent sets and closed-shell independent sets of fullerenes
… to finding a graph-theoretical maximum independent set: a vertex subset of maximum size such that no two vertices are adjacent. The problem of determining the maximum independent set order is NP-hard for general cubic planar graphs and the complexity for the fullerene subclass was …
-
Solving lattice protein problems with quantum computing
… computers may offer advantages for certain problems. Although a few algorithms have proven speedups, it remains unclear where quantum computers will be practically useful, especially since current devices are noisy, small, and not yet fault tolerant. This thesis explores quantum computing …
-
Near-Term Quantum Algorithms for Classical Sampling
… counterparts [26]. However, the sampling problems considered often do not possess immediate practical relevance. This thesis explores two quantum algorithms for applicable classical sampling problems that can be implemented on today’s quantum devices. Specifically, we are considering …
-
Boundary Independent Broadcasts in Graphs
… on a connected graph $G$ with vertex set $V(G)$ is a function $f:V(G)\rightarrow \{0, 1, ..., \text{diam}(G)\}$ such that $f(v)\leq e(v)$, where $e(v)$ denotes the eccentricity of $v$. A vertex $v$ is said to be \textit{broadcasting} if $f(v)>0$. The \textit{cost} of $f$ is …
-
Graph theoretic generalizations of clique: optimization and extensions
… theoretic generalizations of the maximum clique problem. Models that were originally proposed in social network analysis literature, are investigated from a mathematical programming perspective for the first time. A social network is usually represented by a graph, and cliques were the first …
-
Parameterized Approximation Results for Clustering and Graph Packing Problems
… geometry, and operations research. Many central problems in these domains are known to be NP-hard, prompting the exploration of approximation algorithms and parameterized algorithms as possible approaches, among others. In recent times, the paradigm of parameterized approximation algorithms, …
Page 1 of 2