Show simple item record

dc.contributor.authorFast, Caleb C.
dc.date.accessioned 2018-06-19T17:51:22Z
dc.date.available 2018-06-19T17:51:22Z
dc.date.issued 2017-05
dc.identifier.citation Fast, Caleb C.. "Novel Techniques for the Zero-Forcing and p-Median Graph Location Problems." (2017) https://hdl.handle.net/1911/102254.
dc.identifier.urihttps://hdl.handle.net/1911/102254
dc.descriptionThis work was also published as a Rice University thesis/dissertation: http://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.extent 193 pp
dc.title Novel Techniques for the Zero-Forcing and p-Median Graph Location Problems
dc.type Technical report
dc.date.note May 2017
dc.identifier.digital TR17-08
dc.type.dcmi Text


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record