An almost-greedy search on random binary vectors and random graphs

DOI10.1006/JAGM.2000.1140MaRDI QIDQ2746439zbMATH OpenOpenAlexFDO

Authors Avner Dor, Eitan Greenshtein

Publication date 10 October 2001

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.2000.1140

zbMATH Keywords

search algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deterministic and probabilistic binary search in graphs
• Greedy Search on the Binary Tree with Random Edge-Weights
• scientific article; zbMATH DE number 1875441
• On the search path length of random binary skip graphs
• Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
• On the power of random greedy algorithms
• Almost discrete search programs on graphs
• scientific article; zbMATH DE number 3857170
• A greedy algorithm for finding a large 2‐matching on a random cubic graph
• Searches on a Binary Tree with Random Edge-Weights

Cited in

(5)

• Deterministic Decentralized Search in Random Graphs
• The Greedy Search Algorithm on Binary Vectors
• Optimal and myopic search in a binary random vector
• Analysis of an Exhaustive Search Algorithm in Random Graphs and the $n^{c\log n}$-Asymptotics
• Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs

This page was built for publication: An almost-greedy search on random binary vectors and random graphs

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