Algorytm wyznaczania wielo-towarowego maksymalnego przepływu w grafach skierowanych

• Autorzy: Schiff K.

Warianty tytułu

EN

An algorithm for finding an multi-commodity maximum flow in a directed graph

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono algorytm wyznaczania maksymalnego przepływu wielo-towarowego w oparciu o algorytm Dinica wyznaczania maksymalnego przepływu jedno-towarowego. Algorytmem Dinica wyznaczono ścieżki i płynące nimi strumienie miedzy każda parą s-t. Idea zaprezentowanego algorytmu polega na umożliwieniu przepływu towarów krawędziami wchodzącymi w skład wyznaczonych ścieżek w sposób zrównoważony. Ograniczeniu podlegają jedynie strumienie o największych wartościach.

EN

In this paper algorithm for maximum multi-commodity flow problem, which is based on Dinic's algorithm for maximum flow problem, is presented. Maximum flow is computed for each transported commodity between s-t vertices throughout the network graph using Dinic's algorithm. Each commodity could be transported by different flows moving throughout different paths. The idea of presented algorithm rely on balancing of all flows by using calculated current capacity for each edge in network.

Słowa kluczowe

PL

maksymalny całkowitoliczbowy przepływ wielo-towarowy; grafy skierowane

EN

integer multi-commodity flow problem; directed graph

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2011
• Tom: nr 2
• Opis fizyczny: Pełny tekst na CD, Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Schiff K.

• Politechnika Krakowska,

Bibliografia

• [1] Ford L.R, Fulkerson D.R.: Flows in networks, Princeton Press, Princeton, NJ 1962.
• [2] Dinic E.A.: Algorithm for solution of a problem of maximum flow in a network with power estimation, Sov Math Dok 11, 1970, 1277-80.
• [3] Chiou S.W.: Faster combinatorial approximation algorithms for multi-commodity flow problems and its applications, Workshop on Algorithms and Computational Molecular Biology, International Computers Symposium, Taiwan 2002.
• [4] Leighton T., Makedon F., Plotkin S., Tardos C., Tragoudas S.: Fast approximation algorithms for multi-commodity flow problem, Journal of Computer and Systems Science, 50, 228-243,1995.
• [5] Goldberg A., Oldham J.D., Plotkin S., Stein C.: An implementation of a combinatorial approximation algorithm for minimum-cost multi-commodity flow, Report No. CS-TR- 97-1600, Department of Computer Science Stanford University, California 1997.
• [6] Plotkin S.A., Shmoys D.B., Tardos E.: Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operational Research, 20(2), 257-301, 1995.
• [7] Radzik T.: Experimental study of a solution method for multi-commodity flow problems, Workshop on Algorithm Engineering and Experiments, 2000.
• [8] Hu T.C.: Multi-commodity network flow, Oper. Res. 11,344-360 1963.
• [9] Sedeno-Noda A., Gonzalez-Martin C., Alonso-Rodrigez S.: A new strategy for the undirected two-commodity maximum flow problem, Raport Departamento de Estadistica, Investigacion Operativa y Computation, Universidad de La Laguna, Tenerife Spain 2008.
• [10] Ahuja R., Magnanti T., Orlin J.B.: Network flows, Prentice-Hall, Englewood Cliffs 1993.
• [11] Kleinberg J., Rabani Y., Tardos E.: Fairness in routing and load balancing, In Proc. Of 35th Annual Symposium on Foundations of Computer Science, 1999.
• [12] Karp R.: On the computational complexity of combinatorial problems, Networks, vol5.no1.,45-68, 1975.
• [13] Wang I-Lin: Shortest paths and multicommodity network flow, Ph.D dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology 2003.
• [14] Costa M.Ch., Letocart L., Roupin F.: Minimal multicut and maximal integer multiflow: A survey, European Journal of Operation Research 162 (2005), 55-69.
• [15] Barnhart C., Hane C., Vance P.: Using branch-and-price to solve origin-destination integer multicommodity flow problem, Operations Research 32(3), 1998, 208-220.
• [16] Costa M.C., Hertz A., Mittaz M.: Bounds and heuristics for the shortest capacitated paths problem, Journal of heuristics 8 (4), 2002, 449-466.
• [17] Costa M.C., Monclar F.R., Zrikem M.: Variable neighborhood search for the optimization of cable layout problem, Jour. of Intelligent Manufacturing 13 (5), 2002, 353-365.