Local versus global search in channel graphs. Issue 1 (7th January 2013)

• Record Type: Journal Article
• Authors: Hunter, A.H.; Pippenger, Nicholas
• Is Part Of: Networks. Volume 62:Issue 1(2013:Aug.)
• Page Start: 27
• Page End: 34
• Publication Date: 2013-01-07
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21489
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>Previous studies of search in channel graphs have assumed global search, for which 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 average, when search must be local than when it may be global. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013</p> </abstract>