blogger visitor

Techucation

A Blog by Malcolm Yoke Hean Low



View Malcolm Low's profile on LinkedIn

Malcolm Low

Create Your Badge

 Subscribe in a reader


Enter your email address:

Delivered by FeedBurner


Archive for November 2006

Ford-Fulkerson Method for Solving Maximum-Flow Problems

Posted on Wednesday, November 22, 2006 at 10:47 PM by Malcolm

Maximum-Flow Problems

  • Given the a network has p nodes.
  • Let N be the set of nodes, N={s0, n_1, n_2, ..., n_p-1 n_p, si}, where s0 and si represent the source and sink of the network.
  • Let N(i) be the ith node in N. So N(0) is the source and N(p+1) is the sink.
  • Given the there are q arcs connecting the nodes in the network. This include a virtual arc that connects from the sink si back to the source s0.
  • Let x(i,j) be the arc linking from node N(i) to node N(j).
  • Each arc x(i,j) has a maximum capacity given by x(i,j).mc. The virtual arc x(p+1,0) has unlimited capacity.
  • Each arc x(i,j) has a current flow given by x(i,j).cf.
  • For a flow to be feasible, it must have the following characteristics:
    • For each arc x(i,j), 0 <= x(i,j).cf <= x(i,j).mc.
    • For each node N(i), sum(x(j,i).cf) for all j=sum(x(i,k).cf for all k
  • The maximum flow problem is then to maximize the flow from the source to the sink, which is the same as maximizing the flow from the sink to the source, x(p+1,0).cf

Ford-Fulkerson Method for Solving Maximum-Flow Problems

  • Initialization: Set all x(i,j).cf to 0. This represents a feasible flow of the network.
  • Let I be the set of arcs x(i,j) where x(i,j).cf< x(i,j). I represents those arcs whose current flow can be increased.
  • Let R be the set of arcs x(i,j) where x(i,j).cf>0. R represents those arcs whose current flow can be decreased.
  • Carry out the following lableling procedure.
    • Step 1: Label the source.
    • Step 2: Label the nodes and arcs (except the virtual arc x(p+1,0) according to the following rules:
      • If node N(i) is labeled, and node N(j) is unlabeled and arc x(i,j) is in the set I, then label node N(j) and x(i,j). Arc x(i,j) is said to be a forward arc.
      • If node N(j) is unlabeled, and node N(i) is labeled and arc x(j,i) is in the set R, then label node N(j) and arc x(j,i). Arc x(j,i) is said to be a backward arc.
    • Step 3: Continue this labeling process until the sink has been labeled or until no more nodes can be labeled. If the sink has been labeled, adjust the flow according the the two cases described below and report step 2. If the sink cannot be labeled, then the flow is optimal.
  • If the labeling process results in the sink being labeled, then there will be a chain of labeled arcs C leading from the source to the sink. A new feasible flow with increased flow from the source to sink can be obtained by adjusting the the flow of the arcs in C.
  • If C contains entirely of forward arcs.
    • Let k = min(x(i,j).mc-x(i,j).cf)) for all x(i,j) in C.
    • k represents the maximum amount of flow that can increased in all arcs of C without violating all capacity constraint.
    • Increase the flow in each arc in C by k.
  • If C contains some forward arcs and some backward arcs.
    • Let k1 = min(x(i,j).cf) for all x(i,j) in C^R.
    • k1 represents the maximum amount of flow that can be decreased in all arcs of C^R without violating all capacity constraint.
    • Let k2 = min(x(i,j).mc-x(i,j).cf)) for all x(i,j) in C^I.
    • k2 represents the maximum amount of flow that can increased in all arcs of C^I without violating all capacity constraint.
    • Let k=min(k1,k2)
    • Increase the flow of each arc in C^I by k and decrease the flow of each arc in C^R by k.
Edited on: Sunday, November 23, 2008 11:45 AM

Posted in General (RSS), Research (RSS)

Project Report Guidelines - Tables, Figures, Format, References, Resources

Posted on Friday, November 17, 2006 at 3:38 PM by Malcolm

Below are a list of points for preparing technical reports for CIDP, URECA, UROP, IA, FYP, MSc/MEng/PhD:
  • All tables and figures should have a caption and should be cited (referred to) in the main text.
  • References are to be included based on commonly used format in IEEE or ACM conferences. References to web pages or articles should include the URL and the date of retrieval.
  • For full text of conference or journal articles, please use the NTU library digital resources. NTU has subscriptions to databases such as IEEE Xplore, ACM Digital Library, Springer Link, Science Direct. NTU Proxy Bookmarklet is a quick way of obtaining full text articles from some of these databases.
Edited on: Friday, March 27, 2009 12:22 PM

Posted in General (RSS), Research (RSS)

Multi-agent Simulation

Posted on Saturday, November 04, 2006 at 11:20 AM by Malcolm

People Systems

Posted in Research (RSS)