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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
COMPLETELY POSITIVE AND CO-POSITIVE PROGRAMMING: APPLICATIONS IN DISRUPTION RISK MANAGEMENT, POST DISASTER HUMANITARIAN LOGISTICS AND HOMELAND SECURITY GAMES
… to obtaining bounds to $\mathcal{NP}$-hard problems as well as stochastic optimization problem. There are literature establishing the equivalence between completely/co-positive programs and several classic NP-hard problems, such as nonconvex quadratic problem, maximum stable set problem, and …
-
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 …
-
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 …
-
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 …