Back to Search
Start Over
Reconstructing weighted graphs with minimal query complexity
- Source :
-
Theoretical Computer Science . Apr2011, Vol. 412 Issue 19, p1782-1790. 9p. - Publication Year :
- 2011
-
Abstract
- Abstract: In this paper, we consider the problem of reconstructing a hidden weighted graph using additive queries. We prove the following. Let be a weighted hidden graph with  vertices and edges such that the weights on the edges are bounded between  and  for any positive constants  and . For any , there exists a non-adaptive algorithm that finds the edges of the graph using 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 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 . [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 412
- Issue :
- 19
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 59328158
- Full Text :
- https://doi.org/10.1016/j.tcs.2010.12.055