{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/20644"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/20644","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Unbounded unimodal search and pursuit problems","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Goldstein, Arthur Sander"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Reingold, E.M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:45:12Z","date_published":"2011-05-07T12:45:12Z","updated_at":"2026-07-22T22:25:16Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1992 Goldstein, Arthur Sander"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9236469","(UMI)AAI9236469"],"render_values":[{"text":"AAI9236469","href":null,"code":true},{"text":"(UMI)AAI9236469","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/20644","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Reingold, E.M."]},{"key":"dc:creator","label":"Author","values":["Goldstein, Arthur Sander"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:45:12Z","10000-01-01","1992"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1992 Goldstein, Arthur Sander"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9236469","(UMI)AAI9236469","http://hdl.handle.net/2142/20644"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T12:45:12Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9236469.pdf: 3179586 bytes, checksum: 058030260d58c80d61664ea3e15271a3 (MD5) Previous issue date: 1992","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:17Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:02-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Unbounded unimodal search and pursuit problems"]}]}],"canonical_facts":{"dc:contributor":["Reingold, E.M."],"dc:creator":["Goldstein, Arthur Sander"],"dc:date":["2011-05-07T12:45:12Z","10000-01-01","1992"],"dc:description":["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.","Made available in DSpace on 2011-05-07T12:45:12Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9236469.pdf: 3179586 bytes, checksum: 058030260d58c80d61664ea3e15271a3 (MD5) Previous issue date: 1992","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:45:17Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:20:02-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9236469","(UMI)AAI9236469","http://hdl.handle.net/2142/20644"],"dc:language":["eng"],"dc:rights":["Copyright 1992 Goldstein, Arthur Sander"],"dc:subject":["Computer Science"],"dc:title":["Unbounded unimodal search and pursuit problems"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:16Z"}