Graph searching with advice

DOI10.1016/j.tcs.2008.08.020zbMath1163.68015OpenAlexW2174013141MaRDI QIDQ1008727

Nicolas Nisse, David Soguet

Publication date: 30 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.020

zbMATH Keywords

monotonicitygraph searchingbits of advice

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Network protocols (68M12)

Related Items (17)

The cost of monotonicity in distributed graph searching ⋮ Byzantine gathering in polynomial time ⋮ More agents may decrease global work: a case in butterfly decontamination ⋮ Finding the size and the diameter of a radio network using short labels ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Fast rendezvous with advice ⋮ Unnamed Item ⋮ Drawing maps with advice ⋮ Network decontamination under \(m\)-immunity ⋮ Impact of knowledge on election time in anonymous networks ⋮ Connected graph searching ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ On-line search in two-dimensional environment ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Distributed graph searching with a sense of direction ⋮ Topology recognition with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph searching and a min-max theorem for tree-width
• The power of a pebble: Exploring and mapping directed graphs
• Connected Treewidth and Connected Graph Searching
• Distributed Chasing of Network Intruders
• The complexity of searching a graph
• Monotonicity in graph searching
• Compact and localized distributed data structures
• Hundreds of impossibility results for distributed computing
• Oracle size
• Recontamination does not help to search a graph
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring
• Algorithms and Computation
• Tree Exploration with an Oracle
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Graph searching with advice