Creating an oracle, The clique problem itself is NP-hard.

Creating an oracle

Assignment Help Basic Computer Science

Reference no: EM1380794

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'|.

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

Reference no: EM1380794

Questions Cloud

Function that uses a switch statement : To locate nearest numbered cross street for a given avenue address, the following algorithm can be used: cancel last diget of the address, divide by two,

Question about flight function : An airline vice president in charge of operations requires to determine whether the current estimates of flight times are accurate. because there is a larger possiblity of variations due to wether and air traffic in the longer flights.

Describe any other factors you would consider in making : Describe any other factors you would consider in making a decision to continue or discontinue doing business with this organization. State the process you would follow to make your decision, provide your decision, and explain the decision making s..

Discuss the process you would apply to determine : Discuss the process you would apply to determine whether the procedure falls within the RN scope of practice and how you would go about introducing the new procedure with physicians and fellow nurses.

Creating an oracle : The clique problem itself is NP-hard. Thus you may not wish to have an oracle that runs in exponential time. Consider approach to approximate the solution.

Boreki reviews the classification and then places item : How can Boreki use this information? Boreki reviews the classification and then places item A2 into the A category. Why might he do so?

Do you think you can stay competitive in business : Do you think you can stay competitive in business, get acceptable bottom-line results, and still operate in an honest and ethical manner? Why, or why not?

Front end and back end processes of office automation : Discuss the difference between the front end and back-end processes of office automation? Provide some examples in your workplace or that you come into contact with?

Create a program that makes an object : Create a class named Pet, after creating the class, create a program that makes an object of the class and prompts the user to enter the name, type, and age of his pet.

User Account

All Pages