Steiner tree problem heuristic

Reference no: EM131121788

(Steiner Tree Problem Heuristic) We are given a connected graph G with a nonnegative weight aij for each arc (i, j) ∈ A. We assume that if an arc (i, j) is present, the reverse arc (j, i) is also present, and aij = aji. Consider the problem of finding a tree in G that spans a given subset of nodes S and has minimum weight over all such trees. (a) Let W∗ be the weight of this tree. Consider the graph I(G), which has node set S and is complete (has an arc connecting every pair of its nodes). Let the weight for each arc (i, j) of I(G) be equal to the shortest distance in the graph G from the node i ∈ S to the node j ∈ S. Let T be a minimum weight spanning tree of I(G). Show that the weight of T is no greater than 2W

Reference no: EM131121788

Questions Cloud

The k onigsberg bridge problem : (a) Suppose that there existed a second bridge connecting the islands B and C, and also another bridge connecting the land areas A and D. Construct an Euler cycle that crosses each of the bridges exactly once.

Three primary roles of hr : Consider which area of HR you are looking at. The three primary roles of HR are:

Is a universal code of ethics for global businesses needed : Is a universal Code of Ethics for global businesses needed and is it possible? Reading the case and putting yourself in the role of the product manager, what would your immediate gut reaction be

Change management result in an organization : How can understanding this concept help a HR achieve better change management result in an organization?

Steiner tree problem heuristic : (Steiner Tree Problem Heuristic) We are given a connected graph G with a nonnegative weight aij for each arc (i, j) ∈ A. We assume that if an arc (i, j) is present, the reverse arc (j, i) is also present, and aij = aji.

Types of control criteria : What types of control criteria would you expect these companies (Panasonic and Procter & Gamble) to use in evaluating their operations and determining how well they are doing?

Describe the concept of it governance and control objectives : Describe the concepts of IT governance and control objectives for information and related technology (COBIT) and discuss how these concepts apply to an effective information systems audit.

Degree-constrained minimum weight spanning trees : (Degree-Constrained Minimum Weight Spanning Trees) Consider the minimum weight spanning tree problem, subject to the additional constraint that the number of tree arcs that are incident to a single given node s should be no greater than a given in..

The version of the traveling salesman problem : (K-Traveling Salesmen Problem) Consider the version of the traveling salesman problem where there are K salesmen that start at city 1, return to city 1, and collectively must visit all other cities exactly once. Transform the problem into an ordin..

User Account

All Pages