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

What is the meaning of p-persistent, What is the meaning of P-persistent ...

What is the meaning of P-persistent If the medium is idle, transmit with probability p, and delay one time unit with probability (1 - p); if the medium is busy, continue to lis

List all application layer and transport layer protocols, a)  A host is sen...

a)  A host is sending a HTTP request to a HTTP server. In the table below, propose a correct set of source and destination port numbers for segments sent from host to server and fr

Itc597, restore the scrambled bits to their original order

restore the scrambled bits to their original order

Clos network, Clos network This network was organized by Clos (1953).  ...

Clos network This network was organized by Clos (1953).  It is a non-blocking network and gives full connectivity like crossbar network but it also requires significantly minim

Two commands that save the running-config to a tftp server, Name the two co...

Name the two commands that save the running-config to a TFTP server Ans)  Two commands are:- a) copy running tftp  b) write network

What is round trip time, What is Round Trip Time? The duration of time ...

What is Round Trip Time? The duration of time it takes to send a message from one end of a network to the other and back, is known as RTT.

State ethernet frame format, Ethernet Frame Format Consists of sev...

Ethernet Frame Format Consists of seven fields There is No mechanism for acknowledging received frames considered an unreliable medium

Ip message finally reassemble, Concept of how does the IP message finally r...

Concept of how does the IP message finally reassemble?

Describe techniques used in location based services, Question: a) Comp...

Question: a) Compare Bluetooth and WIFI based networks over the following factors: Data rate, Range, Application Focus, Battery Power, Frequency Band, Security. b) Differe

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