Skip to main content

Extended exclusive graph search

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2017-05-12
Authors/Contributors
Author: Sun, Youjiao
Abstract
Graph search is an important research area in both mathematics and computer science with many practical applications such as eliminating a malicious software in a computer network. The graph search problem can be intuitively described as follows: given a set of searchers and a fugitive in a graph, the searchers and fugitive move from vertices to vertices in the graph alternatively and the searchers try to capture the fugitive which tries to escape from the searchers. A major optimization problem in graph search is to find the minimum number of searchers (called search number) to capture the fugitive. There are several well known graph models: node-search, edgesearch, mixed-search and exclusive search. In this thesis, we propose a new search model which is an extension of the exclusive search. We prove the extended exclusive search number for trees. We give the search numbers for the well known graph search models and the extended exclusive search on trees of rings. We also propose heuristic search algorithms for power law graphs based on these models.
Document
Identifier
etd10165
Copyright statement
Copyright is held by the author.
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Gu, Qianping
Member of collection
Download file Size
etd10165_YSun.pdf 593.36 KB

Views & downloads - as of June 2023

Views: 0
Downloads: 0