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.

اخر الاخبار

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

عباس.. طفل فقد والده فوجد في خدمة زائري عاشوراء وطنًا آمنًا

شعبة الخطابة النسوية تواصل إقامة مجالس العزاء في شهر المحرم الحرام

لليوم الخامس.. العتبة العباسية المقدسة تقيم مجلس عزاء في صحن مرقد أبي الفضل العباس (عليه السلام)

قسم الشؤون الفكرية يقيم مجلس عزاء حسيني في العاصمة التنزانية دار السلام

المزيد

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

لمن تجاوز الستين.. عليك بشرب 4 أكواب من القهوة يوميا ؟

الحليب مع العسل.. مزيج يمنحك 7 فوائد صحية

لا تبالغ في التنظيف.. قليل من "الاتساخ" قد يحمي عائلتك

دراسة تكشف علاقة خطيرة بين عمر الأم وصحة مولودها

المزيد

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

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

كيف تساعد الصيانة الوقائية في الحفاظ على كفاءة التكييف في سيارتك ؟

في ظاهرة غريبة حيرت العلماء.. كوكبنا قد يسجل أقصر يوم في التاريخ هذا الصيف!

المزيد

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

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