Matroids and Multicommodity Flows
作者： P.D. Seymour
DOI: 10.1016/S0195-6698(81)80033-9
关键词: Graphic matroid 、 Combinatorics 、 Discrete mathematics 、 Matroid 、 Commodity flow 、 Graph 、 Matroid partitioning 、 Mathematics
摘要: The max-flow min-cut theorem and the two-commodity flow may both be interpreted as equalities between maximum feasible packing of certain circuits a graph minimum capacity cocircuits, thus expressed in matroid terms. We study matroids which similar “ k -commodity theorem” holds. (Thus for = 1 2 it holds polygon graphs.) find example that such bond graphs all ; that, any matroid, if 4, then . obtain excluded minor characterizations every ⩾ 2, also case is still unsolved.
sci-hub.se 参考文章(19)
B Rothschild, A Whinston, PURDUE UNIV LAFAYETTE IND KRANNERT GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION, MULTICOMMODITY NETWORK FLOWS. ,(1969)
G. A. Dirac, A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs Journal of the London Mathematical Society. ,vol. s1-27, pp. 85- 92 ,(1952) , 10.1112/JLMS/S1-27.1.85
P.D Seymour, A note on the production of matroid minors Journal of Combinatorial Theory, Series B. ,vol. 22, pp. 289- 295 ,(1977) , 10.1016/0095-8956(77)90077-6
P.D. Seymour, The matroids with the max-flow min-cut property Journal of Combinatorial Theory, Series B. ,vol. 23, pp. 189- 222 ,(1977) , 10.1016/0095-8956(77)90031-4
Robert E. Bixby, ℓ-matrices and a characterization of binary matroids Discrete Mathematics. ,vol. 8, pp. 139- 145 ,(1974) , 10.1016/0012-365X(74)90060-0
T. Gallai, Über reguläre Kettengruppen Acta Mathematica Hungarica. ,vol. 10, pp. 227- 240 ,(1959) , 10.1007/BF02063301
P. D. Seymour, On Odd Cuts and Plane Multicommodity Flows Proceedings of the London Mathematical Society. ,vol. s3-42, pp. 178- 192 ,(1981) , 10.1112/PLMS/S3-42.1.178
P.D Seymour, Decomposition of regular matroids Journal of Combinatorial Theory, Series B. ,vol. 28, pp. 305- 359 ,(1980) , 10.1016/0095-8956(80)90075-1
P. D. Seymour, On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte Proceedings of the London Mathematical Society. ,vol. s3-38, pp. 423- 460 ,(1979) , 10.1112/PLMS/S3-38.3.423
W. T. Tutte, Matroids and graphs Transactions of the American Mathematical Society. ,vol. 90, pp. 527- 552 ,(1959) , 10.1090/S0002-9947-1959-0101527-3