Finding a spanning tree with minimum sum of arc weights

Assignment Help Basic Computer Science
Reference no: EM131122435

(Minimum Weight Spanning Trees) Given a graph (N , A) and a weight wij for each arc (i, j), consider the problem of finding a spanning tree with minimum sum of arc weights. This is not a shortest path problem and in fact it is not even a special case of the minimum cost flow problem. However, it has a similar graph structure to the one of the shortest path problem. Note that the orientation of the arcs does not matter here. In particular, if (i, j) and (j, i) are arcs, any one of them can participate in a spanning tree solution, and the arc having greater weight can be a priori eliminated.

(a) Consider the problem of finding a shortest path from node 1 to all nodes with arc lengths equal to wij . Give an example where the shortest path spanning tree is not a minimum weight spanning tree.

(b) Let us define a fragment to be a subgraph of a minimum weight spanning tree; for example the subgraph consisting of any subset of nodes and no arcs is a fragment. Given a fragment F, let us denote by A(F) the set of arcs (i, j) such that either i or j belong to F, and if (i, j) is added to F no cycle is closed. Show that if F is a fragment, then by adding to F an arc of A(F) that has minimum weight over all arcs of A(F) we obtain a fragment.

(c) Consider a greedy algorithm that starts with some fragment, and at each iteration, adds to the current fragment F an arc of A(F) that has minimum weight over all arcs of A(F). Show that the algorithm terminates with a minimum weight spanning tree.

(d) Show that the complexity of the greedy algorithm is O(NA), where N is the number of nodes and A is the number of arcs.

(e) The Prim-Dijkstra algorithm is the special case of the greedy algorithm where the initial fragment consists of a single node.

Provide an O(N2), implementation of this algorithm. Hint: Together with the kth fragment Fk, maintain for each j /∈ Fk the node nk(i) ∈ Fk such that the arc connecting j and nk(i) has minimum weight

Reference no: EM131122435

Questions Cloud

Explain what happens to the postmerger earnings : Explain what happens to the postmerger earnings per share figure when a company with a relatively high P/E ratio acquires a company with a lower P/E ratio, assuming that the exchange ratio is based on current stock market prices and no synergy exists..
How would the general anti-avoidance rule affect transaction : Over the past two years, your client, a lawyer in sole practice, has developed several software packages for the preparation of legal contracts. If tax is avoided, how would the general anti-avoidance rule affect the transactions?
What methods do financial analysts use to value merger : What methods do financial analysts use to value merger candidates? What are the limitations of each method?
What are some of the reasons why firms merge with other firm : What are some of the reasons why firms merge with other firms?
Finding a spanning tree with minimum sum of arc weights : Provide an O(N2), implementation of this algorithm. Hint: Together with the kth fragment Fk, maintain for each j /∈ Fk the node nk(i) ∈ Fk such that the arc connecting j and nk(i) has minimum weight
Prepare an accounts payable subsidiary ledger report : Prepare an accounts payable subsidiary ledger report (from the corrected accounts payable subsidiaryledger.
Difference between horizontal vertical conglomerate mergers : Discuss the differences between the following types of mergers: a. Horizontal mergers b. Vertical mergers c. Conglomerate mergers
Give the values of the population parameters : Consider a small population of N = 5 units, labeled 1, 2, 3, 4, 5, with respective y-values 3, 1, 0, 1, 5. Consider a simple random sampling design with a sample size n = 3.
Explain the process of preparing an operations budget : Explain the process of preparing an operations budget. Describe the budgeting control process and explain how significant variances are determined. What are the forecasted revenues for the month?

Reviews

Write a Review

 

Basic Computer Science Questions & Answers

  Exploring oop and its data structures

Writing Assignment: Exploring OOP & its Data Structures Complete and submit Research Problem. Write a five page paper using APA format for references. Object-oriented programming has been adopted widely because of its capability to reuse code.

  Code problem huffman encoding

Given a string s of length at most 104 over the alphabet of lower case latin letters. In the first line output the number k of different symbols and the length l of a binary encoding. In each of the next k lines output a binary code of a symbol in th..

  Determine the value of the following expressions

Determine the value of the following expressions.

  How do we use a driver manager in java

What are the most common kinds of queries in general and how can we use them?

  What line blocks a producer thread when the buffer is full

In the implementation of finite bounded buffer shown in Figure 5.16… What line blocks a producer thread when the buffer is full? What line releases a blocked producer thread when space becomes available?

  Describe a set of two keyboard events to allow

Describe a set of two keyboard events to allow the user to zoom the camera in and out.

  Design a function that takes two parameters

Length of a Month Design a function that takes two parameters: year and month, and returns an integer indicating how many days long that month is. January 2009 was 31 days long, February 2009 was 28 days long, February 2008 was 29 days long, and s..

  Create a separate method to do the calculation

Create a separate method to do the calculation and return the result to the main() method to be displayed. Save the program as Salary.java.Please tell me what IDE that was used to create and will run.

  Define a class to represent time

Define a class to represent time, in military format. Your class should have three private data members.

  Explain the management of high-assurance software

The company does not adduce any additional evidence of assurance. How would you explain to the management of this company why their software is in fact not "high-assurance" software?

  The concept of ethical obligations

Based on the case study, George Tenet and the Last Great Days of the CIA, in Stillman, Chapter 16, write a 45 page paper in which you

  Write program that will calculate square and cube of numbers

Write a program that will calculate square and cube of numbers ranging from 0 to 10. Print the output like the following table (hint: use for loop, to print as a table use printf formatting for width).

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