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:
- set theory - Inaccessible cardinals and Andrew Wiles's proof
- oc.optimization control - how to estimate a polyhedron(convex hull) classifier from data sample
- ca.analysis and odes - Asymptotics of Hermite and hypergeometric function
- nt.number theory - adding an n-th root to Q_p
- soft question - Math Vs Social Science
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment