Design algorithm to find clique in graph

Assignment Help Software Engineering

Reference no: EM1362793

Given an undirected graph G=(V, E) where V={x1, x2,···xn}. A clique is a subgraph G0 of G, where G0=(V0,E0) with V0⊆V, E0⊆E, and for any xi, xj∈V0 with i?=j, (xi,xj)∈ E0. A clique is called m-clique if the cardinality (number of vertices) of V0 is m.

Assume that n » 9 (n is much larger than 9) and it takes O(1) time to check whether (xi,xj) ∈ E.

1. Design an O(n9) algorithm to find a 9-clique in G, if such clique exists; answer "no such a clique" if it does not exist. Please describe your algorithm and sketch its correctness. Pseudocode is NOT required.

2. Prove that a set of vertices is a 9-clique if and only if it can be partitioned into 3 disjoint 3-cliques such that the union of any two of them forms a 6-clique.

3. Show how to find a 9-clique in G in time O(nδ) for some δ < 9, if such a clique exists. Describe your algorithm and sketch its correctness. Pseudocode is NOT required.(Hint: consider the fast matrix multiplication problem.)

Reference no: EM1362793

Questions Cloud

Calculate life insurance to protect financial future : If you are a family of four how would you calculate how much life insurance you would need to protect your financial future?

Show performance-based budgeting process : Explain the three distinct phases of the PPBS process and the specific product each phase produces. What do you think are the primary issues your service will address in its POM

Explain what is the processing time per unit for product : Explain What is the processing time per unit for each product and What is the number of annual time (week hour needed) for each product

Risk factors and approaches to risk reduction : If we have the information about risk factors and approaches to risk reduction, why do some people continue making unhealthy choices? Please give two examples to explain.

Design algorithm to find clique in graph : Design an O(n9) algorithm to find a 9-clique in G, if such clique exists; answer "no such a clique" if it does not exist. Please describe your algorithm and sketch its correctness. Pseudocode is NOT required.

Consolidations and business combination promulgations : Analyze how consolidations and business combination promulgations affect off-balance sheet manipulations. Include research on the development of consolidations and business combination promulgations.

Example of product improved on internet : Describe a product or service that is IMPROVED by being offered over the internet. Either it is improved because of price, service or qualit

What is the magnitude of the electric field : What is the magnitude of the electric field. A 50-gram super ball traveling at 25m/s is bounced off a brick wall and rebounds at 22 m/s. A high speed camera records this event. If the ball is in contact with wall for 3.5 ms, what is the average acc..

Introduction to multiple servings : Can you think of any food items that are commonly regarded as single portions but contain multiple servings?

User Account

All Pages