國立虎尾科技大學 |

Novel Techniques for the Zero-Forcing And p-Median Graph Location Problems.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Novel Techniques for the Zero-Forcing And p-Median Graph Location Problems./
Author:	Fast, Caleb C.
Description:	1 online resource (196 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 79-05(E), Section: B.
Contained By:	Dissertation Abstracts International79-05B(E).
Subject:	Operations research. -
Online resource:	click for full text (PQDT)
ISBN:	9780355382648

Novel Techniques for the Zero-Forcing And p-Median Graph Location Problems.
Fast, Caleb C.

Novel Techniques for the Zero-Forcing And p-Median Graph Location Problems. - 1 online resource (196 pages)

Source: Dissertation Abstracts International, Volume: 79-05(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

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.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355382648Subjects--Topical Terms:

573517
Operations research.
Index Terms--Genre/Form:

554714
Electronic books.

Novel Techniques for the Zero-Forcing And p-Median Graph Location Problems.
LDR:02869ntm a2200385Ki 4500 001 910853
005 20180517112612.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355382648
035 $a (MiAaPQ)AAI10673346
035 $a (MiAaPQ)0187rice:2064Fast
035 $a AAI10673346
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Fast, Caleb C. $3 1182337
245 1 0 $a Novel Techniques for the Zero-Forcing And p-Median Graph Location Problems.
264 0 $c 2017
300 $a 1 online resource (196 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-05(E), Section: B.
500 $a Adviser: Illya V. Hicks.
502 $a Thesis (Ph.D.) $c Rice University $d 2017.
504 $a Includes bibliographical references
520 $a 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.
520 $a 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.
520 $a 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.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Operations research. $3 573517
650 4 $a Mathematics. $3 527692
650 4 $a Computer science. $3 573171
655 7 $a Electronic books. $2 local $3 554714
690 $a 0796
690 $a 0405
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Rice University. $b Computational and Applied Mathematics. $3 1180983
773 0 $t Dissertation Abstracts International $g 79-05B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10673346 $z click for full text (PQDT)