@inproceedings{0abbc34803d841739fae0f44b2a49469,
title = "A Linear Programming Approach for Maximum Integral Multiflow and Minimum Multicut Problems in Unrestricted Network",
abstract = "The minimum cut and maximum flow problems form a well-known pair of dual problems providing a min-max relation. Similarly, the continuous relaxation of the minimum multicut problem is the linear dual of a continuous maximum integral multiflow problem. However, both integer multiflow and multicut problems are known to be NP (Nondeterministic Polynomial)-hard and Max SNP (Strongly Nondeterministic Polynomial)-hard problems in unrestricted graphs/networks. In this paper, we formulate the maximum integral multiflow problem as a linear programming model, and propose a method to obtain a minimum multicut set. The proposed model is solved by a commercial optimization toolbox, CPLEX, with promising results, and so the efficiency and effectiveness of the approach are confirmed.",
keywords = "Integral Multiflow, Linear Programming, Minimum Multicut, Networks",
author = "Siyue Zhang and Yiyong Xiao and Xinhao Cui and Ruiyi Yang",
note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 28th International Conference on Automation and Computing, ICAC 2023 ; Conference date: 30-08-2023 Through 01-09-2023",
year = "2023",
doi = "10.1109/ICAC57885.2023.10275179",
language = "英语",
series = "ICAC 2023 - 28th International Conference on Automation and Computing",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "ICAC 2023 - 28th International Conference on Automation and Computing",
address = "美国",
}