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

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

    qucosa-diss

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

    bu Repository record for On the maximum weighted independent set problem with applications in wireless sensor networks (opens in a new tab)

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

    tamu Repository record for A branch, price, and cut approach to solving the maximum weighted independent set problem (opens in a new tab)

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

    tamu Repository record for Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem (opens in a new tab)

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

    reykjavik Repository record for Approximation algorithms for independent set problems on hypergraphs (opens in a new tab)

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

    nus Repository record for A SEMI-DEFINITE RELAXATION BRANCH-AND-BOUND ALGORITHM FOR BINARY INTEGER QUADRATIC PROBLEMS USING SCIPSUITE (opens in a new tab) Download file for A SEMI-DEFINITE RELAXATION BRANCH-AND-BOUND ALGORITHM FOR BINARY INTEGER QUADRATIC PROBLEMS USING SCIPSUITE (opens in a new tab)

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

    brazil-uerj Repository record for Algoritmo relax-and-cut para o problema do conjunto independente máximo (opens in a new tab)

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

    auckland-ms Repository record for Adiabatic Quantum Computing with QUBO Formulations (opens in a new tab)

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

    uiuc Repository record for A constructive lower bound for cardinality of codebooks capable of correcting multiple deletion and insertions (opens in a new tab)

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

    toronto-retro Repository record for Efficient Algorithms on Cocomparability Graphs via Vertex Orderings (opens in a new tab)

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

    waterloo Repository record for Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation (opens in a new tab)

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

    tamu Repository record for Novel approaches for solving large-scale optimization problems on graphs (opens in a new tab)

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

    uvic Repository record for Independent sets and closed-shell independent sets of fullerenes (opens in a new tab)

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

    lund Repository record for Solving lattice protein problems with quantum computing (opens in a new tab) Download PDF for Solving lattice protein problems with quantum computing (opens in a new tab)

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

    waterloo Repository record for Near-Term Quantum Algorithms for Classical Sampling (opens in a new tab)

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

    uvic Repository record for Boundary Independent Broadcasts in Graphs (opens in a new tab)

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

    tamu Repository record for Graph theoretic generalizations of clique: optimization and extensions (opens in a new tab)

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

    aalto Repository record for Parameterized Approximation Results for Clustering and Graph Packing Problems (opens in a new tab)

Page 1 of 2