Local versus global search in channel graphs

DOI10.1002/NET.21489MaRDI QIDQ5326802zbMATH OpenOpenAlexFDO

Authors A. H. Hunter, Nicholas Pippenger

Publication date 6 August 2013

Published in Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.2526

zbMATH Keywords

search algorithmscircuit switchingpath search

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Searching and sorting (68P10)

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.

Recommendations

• scientific article; zbMATH DE number 1535253
• scientific article; zbMATH DE number 1334210
• Deterministic Decentralized Search in Random Graphs
• Deterministic Decentralized Search in Random Graphs
• Computational Science - ICCS 2004

Cites work

• scientific article; zbMATH DE number 1334210 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• Percolation
• Routing algorithms for switching networks with probabilistic traffic

Cited in

(2)

• Computational Science - ICCS 2004
• Cascade search for preimages and coincidences: global and local versions

This page was built for publication: Local versus global search in channel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326802)