We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Interactive Graph Search

Formal Metadata

Title
Interactive Graph Search
Title of Series
Number of Parts
155
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
We study interactive graph search (IGS), with the conceptual objective of departing from the conventional top-down strategy in searching a poly-hierarchy, a.k.a. a decision graph. In IGS, a machine assists a human in looking for a target node z in an acyclic directed graph G, by repetitively asking questions. In each question, the machine picks a node u in G, asks a human is there a path from u to z?', and takes a boolean answer from the human. The efficiency goal is to locate z with as few questions as possible. We describe algorithms that solve the problem by asking a provably small number of questions, and establish lower bounds indicating that the algorithms are optimal up to a small additive factor. An experimental evaluation is presented to demonstrate the usefulness of our solutions in real-world scenarios.