Local versus global search in channel graphs

DOI10.1002/NET.21489zbMATH Open1269.68113arXiv1004.2526OpenAlexW1923506176MaRDI QIDQ5326802FDOQ5326802

Authors: A. H. Hunter, Nicholas Pippenger 

Publication date: 6 August 2013

Published in: Networks (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Percolation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Routing algorithms for switching networks with probabilistic traffic

Cited In (2)

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

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)