Learning a hidden graph

We study the problem of learning a hidden graph by edge-detecting queries, each of which tells whether a set of vertices induces an edge of the hidden graph or not. We provide a new information-theoretic lower bound and give a more efficient adaptive algorithm to learn a general graph with n vertice...

Full description

Saved in:
Bibliographic Details
Published in:Optimization letters 2014-12, Vol.8 (8), p.2341-2348
Main Authors: Chang, Huilan, Fu, Hung-Lin, Shih, Chih-Huai
Format: Article
Language:English
Subjects:
Computational Intelligence
Mathematics
Mathematics and Statistics
Numerical and Computational Physics
Operations Research/Decision Theory
Optimization
Original Paper
Simulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the problem of learning a hidden graph by edge-detecting queries, each of which tells whether a set of vertices induces an edge of the hidden graph or not. We provide a new information-theoretic lower bound and give a more efficient adaptive algorithm to learn a general graph with n vertices and m edges in m log n + 10 m + 3 n edge-detecting queries.
ISSN:1862-4472
1862-4480
DOI:10.1007/s11590-014-0751-9