Show simple item record

dc.contributor.advisor Hicks, Illya V
dc.creatorFast, Caleb C
dc.date.accessioned 2017-08-01T17:50:49Z
dc.date.available 2017-08-01T17:50:49Z
dc.date.created 2017-05
dc.date.issued 2017-03-31
dc.date.submitted May 2017
dc.identifier.citation Fast, Caleb C. "Novel Techniques for the Zero-Forcing and p-Median Graph Location Problems." (2017) Diss., Rice University. https://hdl.handle.net/1911/96074.
dc.identifier.urihttps://hdl.handle.net/1911/96074
dc.description.abstract 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 p-median solution that is limited to some input support graph. The algorithm can be used to either find an integral solution from a fractional linear programming solution, or it can be used to improve on the solutions given by a pool of heuristics. In either use, the algorithm compares favorably in running time or solution quality to state-of-the-art heuristics. For the zero-forcing problem, this thesis gives both theoretical and computational results. In the theoretical section, I show that the branchwidth of a graph is a lower bound on its zero-forcing number, and I introduce new bounds on the zero-forcing iteration index for cubic graphs. This thesis also introduces a special type of graph structure, a zero-forcing fort, that provides a powerful tool for the analysis and modeling of zero-forcing problems. In the computational section, I introduce multiple integer programming models for finding minimum zero-forcing sets and integer programming and combinatorial branch and bound methods for finding minimum connected zero-forcing sets. While the integer programming methods do not perform better than the best combinatorial method for the basic zero-forcing problem, they are easily adapted to the connected zero-forcing problem, and they are the best methods for the connected zero-forcing problem.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectp-median
zero forcing
integer programming
branch decomposition
branchwidth
facility location
propagation time
dc.title Novel Techniques for the Zero-Forcing and p-Median Graph Location Problems
dc.type Thesis
dc.date.updated 2017-08-01T17:50:50Z
dc.type.material Text
thesis.degree.department Computational and Applied Mathematics
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record