Learning a hidden uniform hypergraph

Huilan Chang*, Hung-Lin Fu, Chih Huai Shih

*Corresponding author for this work

研究成果: Article同行評審

摘要

Motivated by applications in genome sequencing, Grebinski and Kucherov (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(mrlog 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 mrlogn+(6e)rmr+12 queries if the hidden graph has m edges.

原文English
頁(從 - 到)55-62
頁數8
期刊Optimization Letters
12
發行號1
DOIs
出版狀態Published - 1 一月 2018

指紋 深入研究「Learning a hidden uniform hypergraph」主題。共同形成了獨特的指紋。

引用此