Learning a hidden graph
| dc.citation.epage | 2348 | en_US |
| dc.citation.spage | 2341 | en_US |
| dc.citation.woscount | 0 | en_US |
| dc.contributor.author | Chang, Huilan | en_US |
| dc.contributor.author | Fu, Hung-Lin | en_US |
| dc.contributor.author | Shih, Chih-Huai | en_US |
| dc.contributor.department | 應用數學系 | zh_TW |
| dc.contributor.department | Department of Applied Mathematics | en_US |
| dc.date.accessioned | 2015-07-21T11:21:06Z | |
| dc.date.available | 2015-07-21T11:21:06Z | |
| dc.date.issued | 2014-12-01 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.identifier.doi | 10.1007/s11590-014-0751-9 | en_US |
| dc.identifier.issn | 1862-4472 | en_US |
| dc.identifier.journal | OPTIMIZATION LETTERS | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1007/s11590-014-0751-9 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/123884 | |
| dc.identifier.wosnumber | WOS:000345317500015 | en_US |
| dc.language.iso | en_US | en_US |
| dc.subject | Combinatorial search | en_US |
| dc.subject | Graph learning | en_US |
| dc.subject | Competitive group testing | en_US |
| dc.subject | Complex model | en_US |
| dc.title | Learning a hidden graph | en_US |
| dc.type | Article | en_US |