

Research Ph.D. ThesesThe Asymmetric Orientation Control Matching Problem: Analysis and Algorithms
By Lily Briggs
This thesis explores a matching problem we call the Asymmetric by the study of structural controllability from a graphtheoretic perspective, and is also closely related to other useful graph problems, such as the Asymmetric Assignment problem and the Asymmetric Traveling Salesman problem. If we define a partial assignment as a nodedisjoint cover of simple paths and cycles in a digraph, our problem is: given a symmetric, weighted digraph, find a maximum weight asymmetric partial assignment. In this thesis, we analyze the problem's complexity, present a few algorithmic approaches to solving it, and prove some bounds on solution values in trees. We prove that AOCM is NPcomplete, and further, that it is APXhard. We show that the uniformweight case, however, is reducible to finding simple 2matchings in undirected graphs, and is thus polynomially solvable. Next, we show work on a linear programming algorithm using cutting planes, in which we prove several useful theorems for shrinking and reducing the search space for violated cutting planes of two different types. We also analyze four heuristic algorithms, and show that one of them, with a worst case running time of O(m) (where m is the number of edges) finds above 96% of the optimal value in all of our test cases with uniform weights; however, for general weights, we show that a greedy algorithm outperforms all of our other heuristics on all nonbipartite graphs. Finally, we study the problem in the context of trees. We particularly look at the uniformweight version of the problem. In trees, this is equivalent to finding the Hamiltonian completion number of a tree. We generalize the Jacobsthal numbers, a sequence of natural numbers, and show that the nth number in the generalized mJacobsthal sequence is the Hamiltonian completion number of a perfect mary tree of height n. Additionally, we prove a few other bounds on solution values in trees, and under certain graph operations. Finally, we explore the relationship between structural controllability and Optimal Channel Networks, a model for river networks. Return to main PhD Theses page 

