Given an unweighted graph G=(V,E), let the cut function on this graph be defined to be:
C:2VrightarrowmathbbZ such that:
C(S)=|(u,v)inE:uinSwedgevnotinS|
Suppose you have the ability to query C, but otherwise have no knowledge of the edge set E. Is it possible to reconstruct G by making only polynomial (in |V|) 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:
- What is an intuitive view of adjoints? (version 2: functional analysis)
- ag.algebraic geometry - Obstruction bundle for spaces with Kuranishi structure
- kt.k theory homology - Hilbert $C^*$-modules and approximate units
- algorithms - Thousands of rays intersections with Triangles in 3D space
- ag.algebraic geometry - Is there something like Čech cohomology for p-adic varieties?
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment