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 8 of 8 for “"Stable set problem"”.

  1. Clique Relaxations & the Minority Districting Problem

    … through three combinatorial optimization problems. We model each problem on graphs and exploit the inherent structure of the problem to propose novel integer programming formulations, create fixing procedures, and add valid cuts to the problem. We demonstrate the theoretical and …

    rice Repository record for Clique Relaxations & the Minority Districting Problem (opens in a new tab)

  2. On the Polyhedral Lift-and-Project Rank Conjecture for the Fractional Stable Set Polytope

    … being applied recursively to the fractional stable set polytope of a graph. We focus on two related conjectures proposed by Liptak and Tuncel: the N-N_0 Conjecture and Rank Conjecture. First, we look at the algebraic derivation of new valid inequalities by the operators N and N_0. We then …

    waterloo Repository record for On the Polyhedral Lift-and-Project Rank Conjecture for the Fractional Stable Set Polytope (opens in a new tab)

  3. Coloring Algorithms for Graphs and Hypergraphs with Forbidden Substructures

    … of the generalized version of the $r$-Coloring Problem, the $r$-Pre-Coloring Extension Problem and the List $r$-Coloring Problem restricted to hypergraphs and ordered graphs with forbidden substructures. In the context of forbidding non-induced substructure in hypergraphs, we obtain complete …

    waterloo Repository record for Coloring Algorithms for Graphs and Hypergraphs with Forbidden Substructures (opens in a new tab)

  4. Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems

    The objective of a combinatorial optimization problem is to find an element that maximizes a given function defined over a large and possibly high-dimensional finite set. It is often the case that the set is so large that solving the problem by inspecting all the elements is intractable. One …

    waterloo Repository record for Convex Algebraic Geometry Approaches to Graph Coloring and Stable Set Problems (opens in a new tab)

  5. Bilevel Clique Interdiction and Related Problems

    … a formulation of the bilevel clique interdiction problem. Interdiction, a military term, describes the removal of enemy resources. The single level clique interdiction problem describes the attempt of an attacker to interdict a maximum number of cliques. The bilevel form of the problem introduces …

    rice Repository record for Bilevel Clique Interdiction and Related Problems (opens in a new tab)

  6. Clique Generalizations and Related Problems

    A large number of real-world problems can be model as optimization problems in graphs. The clique model was introduced to aid the study of network structure for social interaction. Each vertex represented an actor and the edges represented the relations between them. Nevertheless, the model has …

    rice Repository record for Clique Generalizations and Related Problems (opens in a new tab)

  7. Cutting planes in mixed integer programming: theory and algorithms

    … chapter introduces the mixed integer programming problem. In this chapter, we review the terminology and cover some basic results that find application throughout this thesis. Furthermore, we describe the practical solution of mixed integer programs, and in particular, we discuss the role of …

    gatech Repository record for Cutting planes in mixed integer programming: theory and algorithms (opens in a new tab)