标题: Learning a hidden graph
作者: Chang, Huilan
Fu, Hung-Lin
Shih, Chih-Huai
应用数学系
Department of Applied Mathematics
关键字: Combinatorial search;Graph learning;Competitive group testing;Complex model
公开日期: 1-十二月-2014
摘要: 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 + 10m + 3n edge-detecting queries.
URI: http://dx.doi.org/10.1007/s11590-014-0751-9
http://hdl.handle.net/11536/123884
ISSN: 1862-4472
DOI: 10.1007/s11590-014-0751-9
期刊: OPTIMIZATION LETTERS
起始页: 2341
结束页: 2348
显示于类别:Articles


文件中的档案:

  1. 000345317500015.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.