Describe the steps involved in network simplex method, Computer Networking

Assignment Help:

QUESTION 1:

(a) Define what you understand by the following terms in Network Flows:

i) UnDirected Path
ii) Directed Path
iii) Directed Cycle.
iv) Tree

In each of the above, show the differences in terms of nodes and directions.

(b) In Radix Heap Algorithm, the technique of buckets is employed. However this idea is an extension of Dial's Algorithm. Analyse the complexity of Radix Heap Algorithm referring to:

1. Movement of nodes between buckets
2. Node Selection principle

QUESTION 2:

(a) Below is the algorithm of a flow decomposition algorithm.

begin
Initialize
while y ≠ Φ do
begin
              Select(s, y)
              Search(s, y)
              if a cycle C is found then do
              begin
                            let D = Capacity(C, y)
                            Add Flow(D, C) to cycle flows
                            Subtract Flow(D, C) from y.
              end
              if a path P is found then do
              begin
                           let D = Capacity(P, y)
                           Add Flow(D, P) to path flows
                           Subtract Flow(D, P) from y.
               end
end

Describe the complexity of the following:

i) Selecting the initial node,
ii) Finding a cycle or a path,
iii) Update step.

(b) Explain how Lower Bounds on Arc Flows are eliminated. Show your workings by a mathematical representation or otherwise.

(c) Refer to the diagram below, show how we could always provide a flow of at most 10 on Node 4.

                          1881_11.png

QUESTION 3:

(a) Briefly describe the steps involved in Network Simplex Method.

(b) Referring to Dial's Algorithm and assuming C, to be the Largest arc length, complete the table below.

Variables                                   Cost Value
Number of buckets needed
Time to create buckets.
Time to update d() and
buckets.
Time to find min.
Total running time.

(c) Using Kruskal's algorithm, find the minimum spanning tree of the graph as show in Figure 3.1.

                              1776_11.png

                                                       Figure 3.1

(d) Give mathematical models for the 0-1 knapsack problem and the bounded knapsack problem in Dynamic Programming.


QUESTION 4:

(a) Write down a Generic Label Correcting Algorithm.

(b) Explain how you could detect Negative Cost Cycles in a given set of flows.

(c) Prove that a Negative Cycle Algorithm terminates with an optimal flow.


Related Discussions:- Describe the steps involved in network simplex method

Ports, It is an additional 16-bit number which uniquely identifies the spec...

It is an additional 16-bit number which uniquely identifies the specific service on any given machine on the Internet. Port numbers are 16 bit wide, so each of the computers on the

Computer Information Systems, I am taking a computer information systems cl...

I am taking a computer information systems class for which I have an online test I need done. It will not let me attach all the material that is on the test but someone well versed

Torus, Torus The mesh network with enclose around connections is called...

Torus The mesh network with enclose around connections is called Tours Network.

Subnetting ip addresses, Explain everything you can tell from the following...

Explain everything you can tell from the following: a. 00-01-00-01-13-FD-F4-C0-00-1E-33-92-CE-99 b. fe80::2c1e:18af:749b:91c5%12 c. 2002:8b64:6e3a::8b64:6e3a d. ::0

Operating systems, What everyday object is the same as The RAM function to ...

What everyday object is the same as The RAM function to the computer?

Ip address, how can u identify the ip class of given ip address

how can u identify the ip class of given ip address

Usages, what are usages of gogle and internet

what are usages of gogle and internet

What is error detection, What is Error Detection? What are its methods? ...

What is Error Detection? What are its methods? Data can be corrupted during transmission. For reliable communication errors must be deducted and corrected. Error Detection uses

Determine downloading time when non persistent http is used, Assume that a ...

Assume that a user wants to download from a server a web page that references 3 objects. The base page and each of the objects are of the same size that requires 20 ms transmission

Write Your Message!

Captcha
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