New bounds for search numbers using probabilistic and algorithmic techniques

Tavakoli, Yashar (2012) New bounds for search numbers using probabilistic and algorithmic techniques. Masters thesis, Memorial University of Newfoundland.

[img] [English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Accepted Version
Available under License - 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.

Download (20Mb)
  • [img] [English] PDF - Accepted Version
    Available under License - 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.
    (Original Version)

Abstract

Graph searching is a well-studied subject in graph theory. This thesis concentrates on the magnitude of two different search numbers. First, a new upper bound on the fast search number of a general graph is given. The new result improves the existing bound on the fast search number which is given by the brush number. Based on the improved result, an upper bound for almost all graphs is obtained. Next, using an existing lower bound on the fast search number, a lower bound on the fast search number of almost all graphs is derived. Finally, the only existing upper bound on the node search number of a general graph is improved.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/2399
Item ID: 2399
Additional Information: Includes bibliographical references (leaves 61-64)
Department(s): Science, Faculty of > Mathematics and Statistics
Date: 2012
Date Type: Submission
Library of Congress Subject Heading: Graph theory--Data processing; Mathematics--Graphic methods; Free probability theory; Branch and bound algorithms

Actions (login required)

View Item View Item

Downloads

Downloads per month over the past year

View more statistics