Degree-constrained minimum weight spanning trees

Reference no: EM131121785

(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 integer k. Consider adding a nonnegative weight w to the weight of all incident arcs of node s, solving the corresponding unconstrained spanning tree problem, and gradually increasing w until the degree constraint is satisfied.

(a) State a polynomial algorithm for doing this and derive its running time.

(b) Use this algorithm to solve the problem of Fig. 10.19, where the degree of node 1 is required to be no more than 2.

Reference no: EM131121785

Questions Cloud

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..

Explain how these organizations can benefit you : Explain elements or attributes of these organizations that appeal to you most and you find the most useful. For one of your chosen organizations, explain which elements or attributes are geared toward IT leaders.

A minimum cost spanning tree of the graph : Christofides' Traveling Salesman Heuristic) Consider a symmetric traveling salesman problem where the arc costs are nonnegative and satisfy the triangle inequality (cf. the preceding exercise).

Estimate the daily heat loss through the wall : Assuming quasi steady conditions for which changes in energy storage within the wall may be neglected, estimate the daily heat loss through the wall if its total surface area is 200 m2.

User Account

All Pages