Designing an oracle for a function
Not what you're looking for?
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.
Purchase this Solution
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
Purchase this Solution
Free BrainMass Quizzes
C# variables and classes
This quiz contains questions about C# classes and variables.
Javscript Basics
Quiz on basics of javascript programming language.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.
Excel Introductory Quiz
This quiz tests your knowledge of basics of MS-Excel.