Unbounded unimodal search and pursuit problems

A variation of Kraft's inequality is proven for a unimodal search tree. The inequality is used to prove the near optimality of an algorithm for solving the unbounded discrete unimodal search problem. New results on the computational complexity of determining if capture is possible is obtained for discrete pursuit problems. Similar techniques lead to new complexity results on some combinatorial games. Upper and lower bounds on the time for capture are developed for the continuous Lion-Man problem.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Goldstein, Arthur Sander

Contributors dc:contributor

• Reingold, E.M.

• Computer Science

Statement dc:rights

• Copyright 1992 Goldstein, Arthur Sander

Language dc:language

eng

Identifier

AAI9236469
(UMI)AAI9236469

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/20644