1996 | ReviewPaper | Chapter
Searching a fixed graph
Authors : Elias Koutsoupias, Christos Papadimitriou, Mihalis Yannakakis
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study three combinatorial optimization problems related to searching a graph that is known in advance, for an item that resides at an unknown node. The search ratio of a graph is the optimum competitive ratio (the worst-case ratio of the distance traveled before the unknown node is visited, over the distance between the node and a fixed root, minimized over all Hamiltonian walks of the graph). We also define the randomized search ratio (we minimize over all distributions of permutations). Finally, the traveling repairman problem seeks to minimize the expected time of visit to the unknown node, given some distribution on the nodes. All three of these novel graph-theoretic parameters are NP-complete —and MAXSNP-hard — to compute exactly; we present interesting approximation algorithms for each. We also show that the randomized search ratio and the traveling repairman problem are related via duality and polyhedral separation.