Find a maximum-size independent set if g is a tree

Assignment Help Basic Computer Science

Reference no: EM131366351

An independent set of an undirected graph G = (V,E) is a set of vertices U such that no edge in E is incident on two vertices of U.

(a) Give an efficient algorithm to find a maximum-size independent set if G is a tree.

(b) Let G = (V,E) be a tree with weights associated with the vertices such that the weight of each vertex is equal to the degree of that vertex. Give an efficient algorithm to find a maximum independent set of G.

(c) Let G = (V,E) be a tree with arbitrary weights associated with the vertices. Give an efficient algorithm to find a maximum independent set of G.

Reference no: EM131366351

Questions Cloud

Find the number of different shortest paths : Let v and w be two vertices in a directed graph G = (V,E). Design a lineartime algorithm to find the number of different shortest paths (not necessarily vertex disjoint) between v and w. Note: the edges in G are unweighted.

How was slavery at the center of the expanding trade network : How was slavery at the center of the expanding trade network between Europe and the colonies?

Pounds of groceries into your home each week : Suppose you bring 100 pounds of groceries into your home each week. Please estimate how many pounds of each type of waste leaves your home. Does this add up to 100 pounds? Where do the various forms end up?

Describe the important people or events of american history : American history homework in MLA format based 3 important people or events of American History, I have chosen Dr. Martin Luther King Jr., the Civil Rights Act, and The Great Society as topics.

Find a maximum-size independent set if g is a tree : Let G = (V,E) be a tree with arbitrary weights associated with the vertices. Give an efficient algorithm to find a maximum independent set of G.

Is this assessment different for a global organization : Analyze how the four steps of the control process and explain how each step contributes to the control function. Describe the three types of controls. How can the effectiveness of controls be assessed in an organization? Is this assessment differe..

Different forms of regulation mechanisms : 1. How is gene expression regulated (give three different forms of regulation mechanisms)? 2. How does gene regulation relate to cancer development?

Discuss about the buddhist worldview : Explain what you think about the ways in which the Buddhist worldview is similar to or different from the traditional Western one, and how do both of these compare to the current scientific way of thinking?

Potato slice that was placed into pure water : If you place one potato slice into pure water and another potato slice into a 20% salt solution, which of the following would you expect? a. More water will flow into the potato slice that was placed into pure water.

User Account

All Pages