THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS

THIS PAPER PRESENTS NEW ALGORITHMS FOR THE MAXIMUM FLOW PROBLEM, THE HITCHCOCK TRANSPORTATION PROBLEM, AND THE GENERAL MINIMUM-COST FLOW PROBLEM. UPPER BOUNDS ON THE NUMBERS OF STEPS IN THESE ALGORITHMS ARE DERIVED, AND ARE SHOWN TO COMPARE FAVORABLY WITH UPPER BOUNDS ON THE NUMBERS OF STEPS REQUIRED BY EARLIER ALGORITHMS. THE PAPER STATES THE MAXIMUM FLOW PROBLEM, GIVES THE FORD-FULKERSON LABELING METHOD FOR ITS SOLUTION, AND POINTS OUT THAT AN IMPROPER CHOICE OF FLOW AUGMENTING PATHS CAN LEAD TO SEVERE COMPUTATIONAL DIFFICULTIES. RULES OF CHOICE THAT AVOID THESE DIFFICULTIES ARE GIVEN. A NEW ALGORITHM IS GIVEN FOR THE MINIMUM-COST FLOW PROBLEM, IN WHICH ALL SHORTEST-PATH COMPUTATIONS ARE PERFORMED ON NETWORKS WITH ALL WEIGHTS NONNEGATIVE. /AUTHOR/

• Authors:
  • Edmonds, J
  • KARP, R M
• Publication Date: 1972-4

Media Info

• Features: Figures; References;
• Pagination: p. 248-64
• Serial:
  • Journal Assoc for Computing Machinery
  • Volume: 19
  • Issue Number: 2

Subject/Index Terms

• TRT Terms: Algorithms; Analysis; Network analysis (Planning); Traffic flow; Transportation
• Uncontrolled Terms: Network flows
• Subject Areas: Operations and Traffic Management; Transportation (General);

Filing Info

• Accession Number: 00226334
• Record Type: Publication
• Files: TRIS
• Created Date: May 29 1972 12:00AM