Lower Bounds on Edge Searching

DOI10.1007/978-3-540-74450-4_46MaRDI QIDQ3611939zbMATH OpenOpenAlexFDO

Authors Brian Alspach, Danny Dyer, D. Hanson, Boting Yang

Publication date 3 March 2009

Published in Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74450-4_46

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)

Recommendations

• Lower bounds on fast searching
• Three-fast-searchable graphs
• The complexity of searching a graph
• Fast edge-searching and related problems
• Fast edge searching and fast searching on graphs

Cited in

(14)

• Edge searching weighted graphs
• Standard directed search strategies and their applications
• Sweeping graphs with large clique number
• Complexity and lowers bounds for power edge set problem
• The fast search number of a complete \(k\)-partite graph
• An NP-completeness result of edge search in graphs
• Fast searching on complete k-partite graphs
• Searching and sweeping graphs: a brief survey
• Edge search number of cographs
• Lower bounds in on-line geometric searching metric searching
• Edge Search Number of Cographs in Linear Time
• Lower bounds in on-line geometric searching
• Fast edge searching and fast searching on graphs
• An annotated bibliography on guaranteed graph searching

This page was built for publication: Lower Bounds on Edge Searching

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