Document Type

Article - preprint

Department

Mathematics (HMC)

Publication Date

2010

Abstract

Previous studies of search in channel graphs has assumed that the search is global; that is, that the status of any link can be probed by the search algorithm at any time. We consider for the first time local search, for which only links to which an idle path from the source has already been established may be probed. We show that some well known channel graphs may require exponentially more probes, on the average, when search must be local than when it may be global.

Comments

The definitive version is available at www3.interscience.wiley.com

Rights Information

© 2013 Wiley Periodicals, Inc.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Download

Share

COinS