A heuristic for blocking flow algorithms |
| |
| Affiliation: | 1. Industrial Engineering Department, Galatasaray University, Ortaköy, İstanbul, 34357, Türkiye;2. Industrial Engineering Department, Boğaziçi University, Bebek, İstanbul, 34342, Türkiye;1. FCEIA, Universidad Nacional de Rosario, Pellegrini 250, 2000 Rosario, Argentina;2. CONICET, Argentina;3. Pladema, Universidad Nacional del Centro de la Provincia de Buenos Aires, Campus Universitario Paraje Arroyo Seco, (B7000) Tandil, Buenos Aires, Argentina;1. Rutgers Business School, Newark & New Brunswick Campuses, Rutgers University, 1 Washington Park, Newark, NJ 07102, United States;2. York College, The City University of New York, 94-20 Guy R Brewer Blvd, Jamaica, NY 11451, United States;1. Department of Operations Management, University of Texas at Dallas, Richardson, TX 75080, United States;2. Department of Industrial Engineering, University of Arkansas, Fayetteville, AR 72701, United States |
| |
| Abstract: | This note presents a simple heuristic to speed up algorithms for the maximum flow problem that works by repeatedly finding blocking flows in layered (acyclic) networks. The heuristic assigns a capacity to each vertex of the layered network, which will be an upper bound on the amount of flow that can be transported through that vertex to the sink. This information can be utilized when constructing a blocking flow, since no vertex can ever accommodate more flow than its capacity. The static heuristic computes capacities in a layered network once, while a dynamic variant readjusts capacities during construction of the blocking flow.The effects of both static and dynamic heuristics are evaluated by a series of experiments with the wave algorithm of Tarjan. Although neither give theoretical improvement to the efficiency of the algorithm, the practical effects are in most cases worthwhile, and for certain types of networks quite dramatic. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
