Learning a hidden uniform hypergraph

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

2018-01-01

類型

期刊名稱

OPTIMIZATION LETTERS

卷期與頁次

第 12 卷,頁 55–62

ISSN

1862-4472

語言

英文

摘要

Motivated by applications in genome sequencing, Grebinski andKucherov (Discret Appl Math 88: 147-165, 1998) studied the graph learning problem which is to identify a hidden graph drawn from a given class of graphs with vertex set {1, 2,..., n} by edge-detecting queries. Each query tells whether a set of vertices induces any edge of the hidden graph or not. For the class of all hypergraphs whose edges have size at most r, Chodoriwsky and Moura (Theor Comput Sci 592: 1-8, 2015) provided an adaptive algorithm that learns the class in O(m(r) log n) queries if the hidden graph has m edges. In this paper, we provide an adaptive algorithm that learns the class of all r-uniform hypergraphs in mr log n + (6e)(r)m(r+1/2) queries if the hidden graph has m edges.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Chang, H., Fu, H.-L., & Shih, C.-H. (2018). Learning a hidden uniform hypergraph. OPTIMIZATION LETTERS, 12, 55–62. https://doi.org/10.1007/s11590-017-1131-z

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/144339