Solving the maximum flow problem with the lift-to-front algorithm
Article Sidebar
Published:
Aug 24, 2023
Keywords:
Lift-To-Front, Preflow-Push, Problema Maximum Flow
Section
Computer Science
Statistics Article
Article View : 85 Times
Main Article Content
Abstract
Maximum flow network is an optimization problem related to the effort to optimize the system in maximizing the scale of materials that can be shipped from source to destination based on the system's capabilities. This problem can be solved using the lift-to-front algorithm. The lift-to-front algorithm is based on the application of lists by maintaining a list of vertices in the network. When a vertex is selected it is moved to the front of the list (hence the method is called 'lift-to-front') and the method starts its review once again. The results show that the designed software can demonstrate the application of the Lift-to-Front Algorithm in solving the Maximum Flow problem.
Downloads
Download data is not yet available.
Article Details
How to Cite
Manurung, H., Ginting, T., Surbakti, A., Harahap, J. and Sembiring, R. (2023) “Solving the maximum flow problem with the lift-to-front algorithm”, Jurnal Mantik, 7(2), pp. 1409-1414. Available at: https://iocscience.org/ejournal/index.php/mantik/article/view/3996 (Accessed: 21April2026).
References
Akram, M., Habib, A., & Allahviranloo, T. (2022). A new maximal flow algorithm for solving optimization problems with linguistic capacities and flows. Information Sciences, 612, 201–230. https://doi.org/10.1016/j.ins.2022.08.068
Almufti, S. M., Marqas, R. B., Othman, P. S., & Sallow, A. B. (2021). Single-based and Population-based Metaheuristics for Solving NP-hard Problems. Iraqi Journal of Science. https://doi.org/10.24996/10.24996/ijs.2021.62.5.34
Alridha, A., Salman, A. M., & Al-Jilawi, A. S. (2021). The Applications of NP-hardness optimizations problem. Journal of Physics: Conference Series, 1818(1), 012179. https://doi.org/10.1088/1742-6596/1818/1/012179
Au-Yeung, R., Chancellor, N., & Halffmann, P. (2023). NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems. Frontiers in Quantum Science and Technology, 2. https://www.frontiersin.org/articles/10.3389/frqst.2023.1128576
Cárdenas-Montes, M. (2018). Creating hard-to-solve instances of travelling salesman problem. Applied Soft Computing, 71, 268–276. https://doi.org/10.1016/j.asoc.2018.07.010
Cheriyan, J., & Mehlhorn, K. (1999). An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters, 69(5), 239–242. https://doi.org/10.1016/S0020-0190(99)00019-8
Duan, Z., Sun, H., Wu, C., & Hu, H. (2022). Flow-network based dynamic modelling and simulation of the temperature control system for commercial aircraft with multiple temperature zones. Energy, 238, 121874. https://doi.org/10.1016/j.energy.2021.121874
Fomin, F. V., Golovach, P. A., Lochet, W., Sagunov, D., Saurabh, S., & Simonov, K. (2023). Detours in directed graphs. Journal of Computer and System Sciences, 137, 66–86. https://doi.org/10.1016/j.jcss.2023.05.001
Gurski, F., Rehs, C., & Rethmann, J. (2019). Knapsack problems: A parameterized point of view. Theoretical Computer Science, 775, 93–108. https://doi.org/10.1016/j.tcs.2018.12.019
Hu, Y., Zhao, X., Liu, J., Liang, B., & Ma, C. (2020). An Efficient Algorithm for Solving Minimum Cost Flow Problem with Complementarity Slack Conditions. Mathematical Problems in Engineering, 2020, e2439265. https://doi.org/10.1155/2020/2439265
Huang, S., & Li, Z. (2023). Vertex-critical (P5,chair)-free graphs. Discrete Applied Mathematics, 341, 9–15. https://doi.org/10.1016/j.dam.2023.07.014
Jensen, P. M., Jeppesen, N., Dahl, A. B., & Dahl, V. A. (2023). Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(02), 2310–2329. https://doi.org/10.1109/TPAMI.2022.3170096
Kumudakshi, Hegde, S. M., & Anusha. (2022). On sequential directed graphs. Materials Today: Proceedings, 54, 738–742. https://doi.org/10.1016/j.matpr.2021.11.028
Kyi, M. T., & Naing, L. L. (2018). Application of Ford-Fulkerson Algorithm to Maximum Flow in Water Distribution Pipeline Network. International Journal of Scientific and Research Publications (IJSRP), 8(12). https://doi.org/10.29322/IJSRP.8.12.2018.p8441
Li, Q., Zhang, T., Chen, C. L. P., Yi, K., & Chen, L. (2022). Residual GCB-Net: Residual Graph Convolutional Broad Network on Emotion Recognition. IEEE Transactions on Cognitive and Developmental Systems, 1–1. https://doi.org/10.1109/TCDS.2022.3147839
Li, W., Ding, Y., Yang, Y., Sherratt, R. S., Park, J. H., & Wang, J. (2020). Parameterized algorithms of fundamental NP-hard problems: A survey. Human-Centric Computing and Information Sciences, 10(1), 29. https://doi.org/10.1186/s13673-020-00226-w
Monis, L., Kunjumon, B., & Guruprasad, N. (2019). Implementation of Maximum Flow Algorithm in an Undirected Network. In V. Sridhar, M. C. Padma, & K. A. R. Rao (Eds.), Emerging Research in Electronics, Computer Science and Technology (pp. 195–202). Springer. https://doi.org/10.1007/978-981-13-5802-9_18
Mor, B., Shabtay, D., & Yedidsion, L. (2021). Heuristic algorithms for solving a set of NP-hard single-machine scheduling problems with resource-dependent processing times. Computers & Industrial Engineering, 153, 107024. https://doi.org/10.1016/j.cie.2020.107024
Murua, M., Galar, D., & Santana, R. (2022). Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm. Journal of Computational Science, 60, 101578. https://doi.org/10.1016/j.jocs.2022.101578
Orkun Baycik, N. (2022). Machine learning based approaches to solve the maximum flow network interdiction problem. Computers & Industrial Engineering, 167, 107873. https://doi.org/10.1016/j.cie.2021.107873
?uvak, Z., Alt?nel, ?. K., & Aras, N. (2020). Exact solution algorithms for the maximum flow problem with additional conflict constraints. European Journal of Operational Research, 287(2), 410–437. https://doi.org/10.1016/j.ejor.2020.04.001
Wu, J., Cheng, Y., Yang, Z., & Chu, F. (2023). A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints. Operations Research Letters, 51(5), 473–476. https://doi.org/10.1016/j.orl.2023.07.003
Zhou, J., Yuan, C., Qian, Z.-Y., Wang, B.-H., & Nie, S. (2023). Analysis of cut vertex in the control of complex networks. Chinese Physics B, 32(2), 028902. https://doi.org/10.1088/1674-1056/aca208
Almufti, S. M., Marqas, R. B., Othman, P. S., & Sallow, A. B. (2021). Single-based and Population-based Metaheuristics for Solving NP-hard Problems. Iraqi Journal of Science. https://doi.org/10.24996/10.24996/ijs.2021.62.5.34
Alridha, A., Salman, A. M., & Al-Jilawi, A. S. (2021). The Applications of NP-hardness optimizations problem. Journal of Physics: Conference Series, 1818(1), 012179. https://doi.org/10.1088/1742-6596/1818/1/012179
Au-Yeung, R., Chancellor, N., & Halffmann, P. (2023). NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems. Frontiers in Quantum Science and Technology, 2. https://www.frontiersin.org/articles/10.3389/frqst.2023.1128576
Cárdenas-Montes, M. (2018). Creating hard-to-solve instances of travelling salesman problem. Applied Soft Computing, 71, 268–276. https://doi.org/10.1016/j.asoc.2018.07.010
Cheriyan, J., & Mehlhorn, K. (1999). An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters, 69(5), 239–242. https://doi.org/10.1016/S0020-0190(99)00019-8
Duan, Z., Sun, H., Wu, C., & Hu, H. (2022). Flow-network based dynamic modelling and simulation of the temperature control system for commercial aircraft with multiple temperature zones. Energy, 238, 121874. https://doi.org/10.1016/j.energy.2021.121874
Fomin, F. V., Golovach, P. A., Lochet, W., Sagunov, D., Saurabh, S., & Simonov, K. (2023). Detours in directed graphs. Journal of Computer and System Sciences, 137, 66–86. https://doi.org/10.1016/j.jcss.2023.05.001
Gurski, F., Rehs, C., & Rethmann, J. (2019). Knapsack problems: A parameterized point of view. Theoretical Computer Science, 775, 93–108. https://doi.org/10.1016/j.tcs.2018.12.019
Hu, Y., Zhao, X., Liu, J., Liang, B., & Ma, C. (2020). An Efficient Algorithm for Solving Minimum Cost Flow Problem with Complementarity Slack Conditions. Mathematical Problems in Engineering, 2020, e2439265. https://doi.org/10.1155/2020/2439265
Huang, S., & Li, Z. (2023). Vertex-critical (P5,chair)-free graphs. Discrete Applied Mathematics, 341, 9–15. https://doi.org/10.1016/j.dam.2023.07.014
Jensen, P. M., Jeppesen, N., Dahl, A. B., & Dahl, V. A. (2023). Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(02), 2310–2329. https://doi.org/10.1109/TPAMI.2022.3170096
Kumudakshi, Hegde, S. M., & Anusha. (2022). On sequential directed graphs. Materials Today: Proceedings, 54, 738–742. https://doi.org/10.1016/j.matpr.2021.11.028
Kyi, M. T., & Naing, L. L. (2018). Application of Ford-Fulkerson Algorithm to Maximum Flow in Water Distribution Pipeline Network. International Journal of Scientific and Research Publications (IJSRP), 8(12). https://doi.org/10.29322/IJSRP.8.12.2018.p8441
Li, Q., Zhang, T., Chen, C. L. P., Yi, K., & Chen, L. (2022). Residual GCB-Net: Residual Graph Convolutional Broad Network on Emotion Recognition. IEEE Transactions on Cognitive and Developmental Systems, 1–1. https://doi.org/10.1109/TCDS.2022.3147839
Li, W., Ding, Y., Yang, Y., Sherratt, R. S., Park, J. H., & Wang, J. (2020). Parameterized algorithms of fundamental NP-hard problems: A survey. Human-Centric Computing and Information Sciences, 10(1), 29. https://doi.org/10.1186/s13673-020-00226-w
Monis, L., Kunjumon, B., & Guruprasad, N. (2019). Implementation of Maximum Flow Algorithm in an Undirected Network. In V. Sridhar, M. C. Padma, & K. A. R. Rao (Eds.), Emerging Research in Electronics, Computer Science and Technology (pp. 195–202). Springer. https://doi.org/10.1007/978-981-13-5802-9_18
Mor, B., Shabtay, D., & Yedidsion, L. (2021). Heuristic algorithms for solving a set of NP-hard single-machine scheduling problems with resource-dependent processing times. Computers & Industrial Engineering, 153, 107024. https://doi.org/10.1016/j.cie.2020.107024
Murua, M., Galar, D., & Santana, R. (2022). Solving the multi-objective Hamiltonian cycle problem using a Branch-and-Fix based algorithm. Journal of Computational Science, 60, 101578. https://doi.org/10.1016/j.jocs.2022.101578
Orkun Baycik, N. (2022). Machine learning based approaches to solve the maximum flow network interdiction problem. Computers & Industrial Engineering, 167, 107873. https://doi.org/10.1016/j.cie.2021.107873
?uvak, Z., Alt?nel, ?. K., & Aras, N. (2020). Exact solution algorithms for the maximum flow problem with additional conflict constraints. European Journal of Operational Research, 287(2), 410–437. https://doi.org/10.1016/j.ejor.2020.04.001
Wu, J., Cheng, Y., Yang, Z., & Chu, F. (2023). A 3/2-approximation algorithm for the multiple Hamiltonian path problem with no prefixed endpoints. Operations Research Letters, 51(5), 473–476. https://doi.org/10.1016/j.orl.2023.07.003
Zhou, J., Yuan, C., Qian, Z.-Y., Wang, B.-H., & Nie, S. (2023). Analysis of cut vertex in the control of complex networks. Chinese Physics B, 32(2), 028902. https://doi.org/10.1088/1674-1056/aca208
Copyright and Licensing
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.