Given an unweighted graph , let the cut function on this graph be defined to be:
such that:
Suppose you have the ability to query , but otherwise have no knowledge of the edge set . Is it possible to reconstruct by making only polynomial (in ) many queries to the cut function?
Monday, 13 August 2007
algorithms - Reconstructing a graph given access to its cut function
at
14:17
Labels:
Mathematics

Related Posts:
- dg.differential geometry - Two definitions of Calabi-Yau manifolds
- soft question - Colloquial catchy statements encoding serious mathematics
- The 'real' use of Quantum Algebra, Non-commutative Geometry, Representation Theory, and Algebraic Geometry to Physics
- lo.logic - Is there a computable model of ZFC?
- ag.algebraic geometry - how good an approximation to the equivariant derived category is given by the Grassmannian filtration of the classifying space?
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment