کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437410 | 690135 | 2011 | 9 صفحه PDF | دانلود رایگان |
In this paper, we consider the problem of reconstructing a hidden weighted graph using additive queries. We prove the following. Let GG be a weighted hidden graph with nn vertices and mm edges such that the weights on the edges are bounded between n−an−a and nbnb for any positive constants aa and bb. For any mm, there exists a non-adaptive algorithm that finds the edges of the graph using O(mlognlogm) additive queries. This solves the open problem in [S. Choi, J.H. Kim, Optimal query complexity bounds for finding graphs, in: STOC, 2008, pp. 749–758].Choi and Kim’s proof holds for m≥(logn)αm≥(logn)α for a sufficiently large constant αα and uses the graph theory. We use the algebraic approach for the problem. Our proof is simple and holds for any mm.
Journal: Theoretical Computer Science - Volume 412, Issue 19, 22 April 2011, Pages 1782–1790