Algorithmic complexity and extremality characterizations for edge searching and its variations
Thesis (Ph.D.)--Memorial University of Newfoundland, 2008. Mathematics and Statistics Includes bibliographical references (leaves 94-99) Edge searching is a combinatorial game played on graphs. The aim is to construct a search strategy to catch an intruder hidden in the graph independent of his acti...
Main Author: | |
---|---|
Other Authors: | |
Format: | Thesis |
Language: | English |
Published: |
2008
|
Subjects: | |
Online Access: | http://collections.mun.ca/cdm/ref/collection/theses4/id/27161 |
id |
ftmemorialunivdc:oai:collections.mun.ca:theses4/27161 |
---|---|
record_format |
openpolar |
spelling |
ftmemorialunivdc:oai:collections.mun.ca:theses4/27161 2023-05-15T17:23:33+02:00 Algorithmic complexity and extremality characterizations for edge searching and its variations Yasar, Oznur, 1978- Memorial University of Newfoundland. Dept. of Mathematics and Statistics 2008 viii, 101 leaves : ill. (some col.) Image/jpeg; Application/pdf http://collections.mun.ca/cdm/ref/collection/theses4/id/27161 Eng eng Electronic Theses and Dissertations (9.85 MB) -- http://collections.mun.ca/PDFs/theses/Yasar_Oznur.pdf a2707752 http://collections.mun.ca/cdm/ref/collection/theses4/id/27161 The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Paper copy kept in the Centre for Newfoundland Studies, Memorial University Libraries Combinatorial group theory Graph algorithms Text Electronic thesis or dissertation 2008 ftmemorialunivdc 2015-08-06T19:21:53Z Thesis (Ph.D.)--Memorial University of Newfoundland, 2008. Mathematics and Statistics Includes bibliographical references (leaves 94-99) Edge searching is a combinatorial game played on graphs. The aim is to construct a search strategy to catch an intruder hidden in the graph independent of his actions. If the intruder has a diffused form then searching corresponds to cleaning the graph. A related problem consists of minimizing the number of searchers used in this search. Various versions of edge searching have been introduced in the past depending on how searchers and the intruder can move. In this dissertation we define Weighted Search and Fast Search as two new variants and answer some complexity and extremality problems. -- Weighted Search corresponds to cleaning a contaminated graph where edges may have different capacities. The main result we have is that Weighted Search is an NP-complete problem. We also give comparison results such as bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize those graphs which two searchers can clean. -- Fast Search is an internal monotone search where no edge is traversed more than once in a non-weighted graph. We present a linear time algorithm to compute a fast search strategy for a given tree. We investigate the fast search strategies for bipartite graphs. -- The construction of k-searchable graphs, those graphs which k searchers can clean, has been of major interest. Graphs that are 1,2 or 3-searchable have been completely characterized previously, whereas characterizing 4-searchable graphs was left as an open problem. We solve this problem partially and give insights for future work. Thesis Newfoundland studies University of Newfoundland Memorial University of Newfoundland: Digital Archives Initiative (DAI) |
institution |
Open Polar |
collection |
Memorial University of Newfoundland: Digital Archives Initiative (DAI) |
op_collection_id |
ftmemorialunivdc |
language |
English |
topic |
Combinatorial group theory Graph algorithms |
spellingShingle |
Combinatorial group theory Graph algorithms Yasar, Oznur, 1978- Algorithmic complexity and extremality characterizations for edge searching and its variations |
topic_facet |
Combinatorial group theory Graph algorithms |
description |
Thesis (Ph.D.)--Memorial University of Newfoundland, 2008. Mathematics and Statistics Includes bibliographical references (leaves 94-99) Edge searching is a combinatorial game played on graphs. The aim is to construct a search strategy to catch an intruder hidden in the graph independent of his actions. If the intruder has a diffused form then searching corresponds to cleaning the graph. A related problem consists of minimizing the number of searchers used in this search. Various versions of edge searching have been introduced in the past depending on how searchers and the intruder can move. In this dissertation we define Weighted Search and Fast Search as two new variants and answer some complexity and extremality problems. -- Weighted Search corresponds to cleaning a contaminated graph where edges may have different capacities. The main result we have is that Weighted Search is an NP-complete problem. We also give comparison results such as bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize those graphs which two searchers can clean. -- Fast Search is an internal monotone search where no edge is traversed more than once in a non-weighted graph. We present a linear time algorithm to compute a fast search strategy for a given tree. We investigate the fast search strategies for bipartite graphs. -- The construction of k-searchable graphs, those graphs which k searchers can clean, has been of major interest. Graphs that are 1,2 or 3-searchable have been completely characterized previously, whereas characterizing 4-searchable graphs was left as an open problem. We solve this problem partially and give insights for future work. |
author2 |
Memorial University of Newfoundland. Dept. of Mathematics and Statistics |
format |
Thesis |
author |
Yasar, Oznur, 1978- |
author_facet |
Yasar, Oznur, 1978- |
author_sort |
Yasar, Oznur, 1978- |
title |
Algorithmic complexity and extremality characterizations for edge searching and its variations |
title_short |
Algorithmic complexity and extremality characterizations for edge searching and its variations |
title_full |
Algorithmic complexity and extremality characterizations for edge searching and its variations |
title_fullStr |
Algorithmic complexity and extremality characterizations for edge searching and its variations |
title_full_unstemmed |
Algorithmic complexity and extremality characterizations for edge searching and its variations |
title_sort |
algorithmic complexity and extremality characterizations for edge searching and its variations |
publishDate |
2008 |
url |
http://collections.mun.ca/cdm/ref/collection/theses4/id/27161 |
genre |
Newfoundland studies University of Newfoundland |
genre_facet |
Newfoundland studies University of Newfoundland |
op_source |
Paper copy kept in the Centre for Newfoundland Studies, Memorial University Libraries |
op_relation |
Electronic Theses and Dissertations (9.85 MB) -- http://collections.mun.ca/PDFs/theses/Yasar_Oznur.pdf a2707752 http://collections.mun.ca/cdm/ref/collection/theses4/id/27161 |
op_rights |
The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. |
_version_ |
1766113220265771008 |