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?

Reviews

Write a Review

 

Software Engineering Questions & Answers

  Difference between private, public and protected variables

Difference between private, public and protected variables

  Information flow complexity

Cyclomatic complexity, monitoring devices, wireless dial-out device with controller, Request for Proposals (RFPs), Weighted IFC

  Draw entity-relationship diagram for heg

Instructors are capable of teaching many different courses. Draw an entity-relationship diagram for HEG (in 3NF).

  Frame diagrams

Prepare a frame diagram for the software systems.

  Develop a dtd for catalog of cars

Develop a DTD for a catalog of cars, where each car has child elements make, model, year, color, engine, number_of_doors, transmission_type, and accessories.

  Create class diagram and write the pseudocode

Design a class named HousePlant. A HousePlant has fields for a name (for example, "Philodendron"), a price (for example, 29.99). Create class diagram and write the pseudocode that defines the class.

  Data flow diagram for new customer support system

A context diagram, also called a Data Flow Diagram (DFD), documents the scope of the new customer support system. It focuses primarily on output from the system.

  Describing rfid systems used in inventory control

Illustrate how are RFID systems used in inventory control and supply chain management? What kinds of relationships are possible in relational database?

  Create an eer mode using traditional eer notation

Create an EER model for the following situation using traditional EER notation, the Visio notation or the supertypes notation. An international school of technology has hired you to create a database management system

  Challenges and difficulties of applying software metrics

How to execute software measurement? Write dwon challenges and difficulties of applying software metrics?

  Internal events by creatinguml one state diagram

Which event driven modeling can be used to illustrate how system responds to external and/or internal events by creating a UML ONE State Diagram.

  Describe relationship between different types of software

Describe the relationship between different types of software and the type of machine with which they are compatible.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd