Optimal reconstruction of graphs under the additive model

Vladimir Grebinski, Gregory Kucherov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)


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 Lindstr6m in [17]. Finally, we consider several particular classes of graphs. We show how an optimal non-adaptive solution of O(n2/log n) queries for general graphs can be obtained.

Original languageEnglish
Title of host publicationAlgorithms - ESA 1997 - 5th Annual European Symposium, Proceedings
EditorsRainer Burkard, Gerhard Woeginger
PublisherSpringer Verlag
Number of pages11
ISBN (Print)3540633979, 9783540633976
Publication statusPublished - 1997
Externally publishedYes
Event5th Annual European Symposium on Algorithms, ESA 1997 - Graz, Austria
Duration: 15 Sep 199717 Sep 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th Annual European Symposium on Algorithms, ESA 1997


Dive into the research topics of 'Optimal reconstruction of graphs under the additive model'. Together they form a unique fingerprint.

Cite this