Abstract
The main goal of this paper is to study the following combinatorial problem: given a finite setE={e 1,e2,...,en} and a subset family σ={S 1,S2,...,S k} ofE, does there exist a treeT with the edge setE such that each induced subgraphT[S i] ofS i is precisely a path (1≤i≤k)?
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bixby, R. E., and Cunningham, W. H., Converting linear programs to network problems,Mathematics of Operations Research,5 (1980), 321–357.
Baston, V. J. D., Rahmouni M. K., and Williams, H. P., The practical conversion of linear programmes to network flow models,European J. of Operational Research,50, (1991), 325–334.
Mulvey, J. M., Testing of a large-scale network optimization program,Math. Program 15 (1978), 291–315.
Ford, L. R., and Fulkerson, D. R., Flows in Networks, Princeton University Press, 1962.
Lawler, E. L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.
Harary, F., Graph Theory, Addison-Wesley, 1969.
Berge, C., Packing problems and hypergraph theory: a survey,Annals of Discrete Math.,4 (1979) 3–37, also: Graphs and Hypergraphs, North-Holland (1973).
Rosenberg, A. L., Interval hypergraphs, in: R. B. Richter (ed.), Graphs and Algorithms,Contemporary Mathematics,89 (1989), 27–44.
Author information
Authors and Affiliations
Additional information
Supported by the National Natural Science Foundation of China.
Rights and permissions
About this article
Cite this article
Yixun, L. A recognition problem in converting linear programming to network flow models. Appl. Math. 8, 76–85 (1993). https://doi.org/10.1007/BF02661994
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02661994