Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

1. Let G-(V, E) be an undirected graph with n nodes. Recall that a subset of the nodes is called an independent set if no

image text in transcribed

1. Let G-(V, E) be an undirected graph with n nodes. Recall that a subset of the nodes is called an independent set if no two of them are joined by an edge. Finding large independent sets is difficult in general; but here we'll see that it can be done efficiently if the graph is "simple" enough. Call a graph G = (V, E) a path if its nodes can be written as v1-v2,-.. , Un with an edge between v and v if and only if the numbers i and j differ by exactly 1. With each node v, we associate a positive integer weight w, Consider, for example, the five-node path drawn in Figure 6.28. The weights are the numbers drawn inside the nodes. The goal in this question is to solve the following problem: Find an independent set in a path G whose total weight is as large as possible. Give an example to show that the following algorithm does not always (a) find an independent set of maximum total weight The "heaviest-first" greedy algorithm Start with S equal to the empty set While some node remains in G Pick a node v of maximum weight Add V to S Delete vi and its neighbors from G Endwhile ReturnS (b) Give an example to show that the following algorithm also does not always find an independent set of maximum total weight. Let S1 be the set of all v wherei is an odd number Let S2 be the set of all v where i is an even number (Note that S and S2 are both independent sets) Determine which of S or S2 has greater total weight, and return this one Figure 6.28 A paths with weights on the nodes. The maximum weight of an independent set is 14 (c) Give an algorithm that takes an n-node path G with weights and returns an independent set of maximum total weight. The running time should be polynomial in n, independent of the values of the weights

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Conceptual Database Design An Entity Relationship Approach

Authors: Carol Batini, Stefano Ceri, Shamkant B. Navathe

1st Edition

0805302441, 978-0805302448

More Books

Students also viewed these Databases questions

Question

4-6 Is there a digital divide? If so, why does it matter?

Answered: 1 week ago