رسالة جامعية
Lower Bounds and Algorithms for Searching Networks
| العنوان: | Lower Bounds and Algorithms for Searching Networks |
|---|---|
| المؤلفون: | Xue, Yuan |
| المساهمون: | Yang, Boting, Zilles, Sandra, Yang, Xue Dong, Mouhoub, Malek, Guo, Chun-Hua, MacGillivray, Gary |
| بيانات النشر: | Faculty of Graduate Studies and Research, University of Regina |
| سنة النشر: | 2019 |
| المجموعة: | oURspace - The University of Regina's Institutional Repository |
| الوصف: | A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Computer Science, University of Regina. xiv, 188 p. ; Research on graph searching has recently gained interest in computer science, mathematics, and physics. This thesis provides new results on two graph search models, namely fast searching and the zero-visibility cops and robber model. Given a graph that contains an invisible fugitive, the fast searching problem is to find the fast search number, i.e., the minimum number of searchers to capture the fugitive in the fast search model. This model was first introduced by Dyer, Yang and Ya¸sar in 2008. Although the literature provides a number of results on fast searching, many properties of the fast search number have not yet been revealed. In this thesis, we give new lower bounds on the fast search number. Using the new lower bounds, we prove an explicit formula for the fast search number of the cartesian product of an Eulerian graph and a path. We also give formulas for the fast search number of variants of the cartesian product. We present an upper bound on the fast search number of hypercubes, and extend the results to a broader class of graphs including toroidal grids. In addition, we examine the complete k-partite graphs and provide lower bounds and upper bounds on their fast search number. We also investigate some special classes of complete k-partite graphs, such as complete bipartite graphs and complete split graphs. We solve the open problem of determining the fast search number of complete bipartite graphs, and present upper and lower bounds on the fast search number of complete split graphs. We also introduce the notion of k-combinable graphs, and propose an efficient method for computing the fast search number of such graphs. The zero-visibility cops and robber game is a variant of Cops and Robbers subject to the constraint that the cops have no information at any time about the location of the robber. ... |
| نوع الوثيقة: | thesis |
| وصف الملف: | application/pdf |
| اللغة: | English |
| العلاقة: | http://hdl.handle.net/10294/9188Test; TC-SRU-9188; https://ourspace.uregina.ca/bitstream/handle/10294/9188/Xue_Yuan_PhD_CS_Spring2020.pdfTest |
| الإتاحة: | http://hdl.handle.net/10294/9188Test https://ourspace.uregina.ca/bitstream/handle/10294/9188/Xue_Yuan_PhD_CS_Spring2020.pdfTest |
| رقم الانضمام: | edsbas.BB85E81D |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |