Share
Explore BrainMass

Designing an oracle for a function

Design an oracle for this function:
void compute_maximum_clique( �);
Input: a graph G(V,E), that is, V is a set of nodes and E is a set of edges connecting nodes in G.
Output: a sub-graph G'(V',E') of G such that for any two nodes u,v in V', there is an edge e=(u,v) in E'. In addition, G' should be the maximum in terms of the size. That is, for any other G'' with the above property, we have |G''| no larger than |G'|.

Hints: The clique problem itself is NP-hard. Thus you may not want to have an oracle that runs in exponential time. Think about approach to approximate the solution. In another word, design an oracle that runs efficiently but may make mistakes in some cases.

Solution Summary

This solution designs an oracle for the following function:
void compute_maximum_clique( �);
Input: a graph G(V,E), that is, V is a set of nodes and E is a set of edges connecting nodes in G.
Output: a sub-graph G'(V',E') of G such that for any two nodes u,v in V', there is an edge e=(u,v) in E'. In addition, G' should be the maximum in terms of the size. That is, for any other G'' with the above property, we have |G''| no larger than |G'|.

Hints: The clique problem itself is NP-hard. Thus you may not want to have an oracle that runs in exponential time. Think about approach to approximate the solution. In another word, design an oracle that runs efficiently but may make mistakes in some cases

$2.19