使用循序式演算法尋找隱藏圖

Abstract

我們考慮如何只使用邊偵測問題(edge-detecting query)的情況下去尋找隱藏圖，邊偵測問題可以回答任何點集合內是否包含至少一條邊。Grebinski以及kucherow[5]提供一個確定性演算法去尋找隱藏的漢米爾頓圈(Hamiltonian cycle)，使用最多Ο(nlog n)個問題；Beigel等人[4]提出一個確定性演算法去解決配對圖(bipartite)，使用八個平行的問題群，總共Ο(nlog n)個問題，尋找隱藏的漢米爾頓圈或是配對圖可以應用到基因排序計劃。Angluin以及陳[2] 針對一般的隱藏圖使用最多12m(log n)個問題。在這個論文中，我們提供一個循序式演算法解決一般的隱藏圖，當此圖點數為n、邊數為m時，最多花費(2log n + 9)m個問題。

We consider the problem of learning a hidden graph using edge-detecting queries in a model where the only allowed operation is to query whether a set of vertices induces an edge of the hidden graph or not. Grebinski and Kucherov [5] give a deterministic adaptive algorithm for learning Hamiltonian cycles using Ο(log n) queries. Beigel et al.[4] describe an 8-round deterministic algorithm for learning matchings using Ο(log n) queries, which has direct application in genome sequencing projects. Angluin and Chen [2] use at most 12m(log n) queries in their algorithm for learning a general graph. In this thesis we present an adaptive algorithm that learns a general graph with n􀝊 vertices and m edges using at most (2log n + 9)m queries.