Network Flow

The network flow problem considers a graph  with a set of sources  and sinks  and for which each edge has an assigned capacity (weight), and then asks to find the maximum flow that can be routed from  to  while respecting the given edge capacities. The network flow problem can be solved in time  (Edmonds and Karp 1972; Skiena 1990, p. 237). It is implemented in the Wolfram Language as FindMaximumFlow[g, source, sink].

---

REFERENCES

Edmonds, J. and Karp, R. M. "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems." J. ACM 19, 248-264, 1972.

Even, S. and Tarjan, R. E. "Network Flow and Testing Graph Connectivity." SIAM J. Comput. 4, 507-518, 1975.

Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ: Princeton University Press, 1962.

Gonery, R. E. and Hu, T. C. "Multiterminal Network Flows." J. SIAM 9, 551-570, 1961.

Orlin, J. B. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm." Proc. 20th ACM Symposium Theorem of Computing. pp. 377-387, 1988.

Skiena, S. "Network Flow." §6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 237-239, 1990.

Skiena, S. S. "Network Flow." §8.4.9 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 297-300, 1997.

Tarjan, R. E. Data Structures and Network Algorithms. Philadelphia, PA: SIAM Press, 1983.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength