Learning a hidden graph

標題:	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
顯示於類別：	期刊論文

文件中的檔案：

若為 zip 檔案，請下載檔案解壓縮後，用瀏覽器開啟資料夾中的 index.html 瀏覽全文。