Skip to Main content Skip to Navigation
Journal articles

Optimal Reconstruction of Graphs under the Additive Model

Vladimir Grebinski 1 Gregory Kucherov 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We study the problem of reconstructing unknown graphs under the additive combinatorial search model. The main result concerns the reconstruction of {\em bounded degree} \/graphs, i.e.\ graphs with the degree of all vertices bounded by a constant $d$. We show that such graphs can be reconstructed in $O(dn)$ non--adaptive queries, which matches the information--theoretic lower bound. The proof is based on the technique of se\-pa\-rating matrices. A central result here is a new upper bound for a general class of separating matrices. As a particular case, we obtain a tight upper bound for the class of $d$--separating matrices, which settles an open question stated by Lindström in~\cite{Lindstrom75}. Finally, we consider several particular classes of graphs. We show how an optimal non--adaptive solution of $O(n^2/\log n)$ queries for general graphs can be obtained. We also prove that trees with unbounded vertex degree can be reconstructed in a linear number of queries by a non--adaptive algorithm.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00099091
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:50:52 AM
Last modification on : Tuesday, December 17, 2019 - 4:16:01 PM

Identifiers

Collections

Citation

Vladimir Grebinski, Gregory Kucherov. Optimal Reconstruction of Graphs under the Additive Model. Algorithmica, Springer Verlag, 2000, 28 (1), pp.104-124. ⟨10.1007=s004530010033⟩. ⟨inria-00099091⟩

Share

Metrics

Record views

108