Optimal Reconstruction of Graphs Under the Additive Model

Abstract : We study the problem of combinatorial search for graphs under the additive model. The main result concerns the reconstruction of 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, that matches the information-theoretic lower bound. The proof is based on the technique of separating matrices. In particular, a new upper bound is obtained for d-separating matrices, that settles an open question stated by Lindström in [16]. 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.
Type de document :
Rapport
[Research Report] RR-3171, INRIA. 1997
Liste complète des métadonnées

https://hal.inria.fr/inria-00073517
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:06:31
Dernière modification le : mardi 6 mars 2018 - 17:40:58
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:49:01

Fichiers

Identifiants

  • HAL Id : inria-00073517, version 1

Collections

Citation

Vladimir Grebinski, Gregory Kucherov. Optimal Reconstruction of Graphs Under the Additive Model. [Research Report] RR-3171, INRIA. 1997. 〈inria-00073517〉

Partager

Métriques

Consultations de la notice

203

Téléchargements de fichiers

231