Fast edge searching and fast searching on graphs

DOI10.1016/j.tcs.2010.12.065zbMath1211.68294OpenAlexW2068825173MaRDI QIDQ631784

Boting Yang

Publication date: 14 March 2011

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

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

zbMATH Keywords

fast searchingcops-and-robber gamesedge searchingpursuit-and-evasion problems

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (11)

Fast-mixed searching and related problems on graphs ⋮ Fast searching on \(k\)-combinable graphs ⋮ Edge searching and fast searching with constraints ⋮ Fast Searching on Complete k-partite Graphs ⋮ Fast searching on cactus graphs ⋮ Three-fast-searchable graphs ⋮ Fast Searching on Cartesian Products of Graphs ⋮ A New Lower Bound for Positive Zero Forcing ⋮ The fast search number of a Cartesian product of graphs ⋮ The fast search number of a complete \(k\)-partite graph ⋮ Positive semidefinite zero forcing numbers of two classes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Cleaning a network with brushes
• The capture time of a graph
• Balanced vertex-orderings of graphs
• Searching and pebbling
• Three-fast-searchable graphs
• On the Fast Searching Problem
• Lower Bounds on Edge Searching
• Lower Bounds on Fast Searching
• Topological Bandwidth
• The complexity of searching a graph
• Monotonicity in graph searching
• Cleaning Regular Graphs with Brushes
• Recontamination does not help to search a graph

This page was built for publication: Fast edge searching and fast searching on graphs