Browsing by Author "Shih, Chih-Huai"

Now showing 1 - 3 of 3

Learning a hidden graph
(2014-12-01)
Chang, Huilan
;
Fu, Hung-Lin
;
Shih, Chih-Huai
;
應用數學系
;
Department of Applied Mathematics
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.
Learning a hidden uniform hypergraph
(2018-01-01)
Chang, Huilan
;
Fu, Hung-Lin
;
Shih, Chih-Huai
;
應用數學系
;
Department of Applied Mathematics
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.
Threshold Group Testing on Inhibitor Model
(2013-06-01)
Chang, Huilan
;
Fu, Hung-Lin
;
Shih, Chih-Huai
;
應用數學系
;
Department of Applied Mathematics
In classical group testing, one is given a population N and an unknown subset D subset of N of positive items, and the goal is to determine D by testing subsets of N. Threshold group testing is a generalization of classical group testing, where the outcome of a group test is determined by the number of positive items in the test. In group testing on inhibitor model, inhibitors are the third type of item that dictate the test outcome to be negative regardless of how many positives are in the test. The threshold group testing on k-inhibitor model is a natural combination of threshold group testing and inhibitor model. In this article, we provide nonadaptive algorithms to conquer the threshold group testing on k-inhibitor model where error-tolerance is considered. Furthermore, we provide a two-stage algorithm to identify all inhibitors and find a g-approximate set.