Back to search

University of Victoria (Canada)

Lower bounds for node search number on grid-like graphs

Abstract

dc:description.abstract

One method to find the node search number of a graph is to prove identical upper and lower bounds. In four types of grid-like graphs. (h. w)-grids. cylinders. orb webs. and walls, upper bounds are easy to see. However. for tori, the upper bounds are less obvious. requiring two different search strategies. In all cases the lower bounds are not obvious and previously unproven. For these five classes of graphs we develop several techniques for proving lower bounds by taking advantage of the fact that re-contamination does help. We observe that in the five classes of graphs we examine, the node search number can be expressed as a function of the height and width of the graph.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Warren, Robert Bramwell
Advisor dc:contributor.supervisor
  • Ellis, John Arthur

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/2179

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Warren, Robert Bramwell. Lower bounds for node search number on grid-like graphs. Master of Science M.Sc. thesis, 2010. http://hdl.handle.net/1828/2179