## Search

Now showing items 1-10 of 11

#### Algorithms to Find the Girth and Cogirth of a Linear Matroid

(2014-09-18)

In this thesis, I present algorithms to find the cogirth and girth, the cardinality of the smallest cocircuit and circuit respectively, of a linear matroid. A set covering problem (SCP) formulation of the problems is ...

#### Bounding the Forcing Number of a Graph

(2015-04-16)

The forcing number, denoted F(G), is an upper bound for the maximum nullity of all symmetric matrices with a sparsity pattern described by the simple graph G. Simple lower and upper bounds are δ ≤ F(G) where δ is the minimum ...

#### Fort Neighborhoods: A Set Cover Formulation for Power Domination

(2018-11-14)

This thesis introduces a novel separation algorithm for calculating power domination
numbers and minimum power dominating sets in graphs. Additionally, it shows how the
existence of solutions of special forms can be exploited ...

#### A Branch and Cut Approach to the Feedback Vertex Set Problem

(2018-11-29)

In this thesis, I use a branch and cut implementation to solve the feedback vertex set problem and add new facet defining inequalities to the literature. Feedback in a system arises when repeated traversal over some cycle ...

#### Novel Techniques for the Zero-Forcing and p-Median Graph Location Problems

(2017-03-31)

This thesis presents new methods for solving two graph location problems, the p-Median problem and the zero-forcing problem. For the p-median problem, I present a branch decomposition based method that finds the best ...

#### Bilevel Clique Interdiction and Related Problems

(2017-04-18)

I introduce 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 ...

#### Clique Generalizations and Related Problems

(2016-04-21)

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

#### A Spectral Decomposition Heuristic for Near Optimal Capture Sets In Consensus Models

(2016-08-31)

Given a network G=(V,E), consider the problem of selecting a subset of nodes, A, of a fixed size, k, such that the sum expected walk length from V to A, or hitting time, is minimized. This study is motivated by modeling ...

#### Efficient Computation of Chromatic and Flow Polynomials

(2015-10-13)

This thesis surveys chromatic and flow polynomials, and presents new efficient methods to compute these polynomials on specific families of graphs. The chromatic and flow polynomials of a graph count the number of ways to ...

#### Graph Coloring, Zero Forcing, and Related Problems

(2017-08-09)

This thesis investigates several problems related to classical and dynamic coloring of graphs, and enumeration of graph attributes. In the first part of the thesis, I present new efficient methods to compute the chromatic ...