Families of cuts with the MFMC-property |
| |
Authors: | A V Karzanov |
| |
Institution: | (1) Institute for Systems Studies, Moscow, USSR |
| |
Abstract: | A family ℱ of cuts of an undirected graphG=(V, E) is known to have the weak MFMC-property if (i) ℱ is the set ofT-cuts for someT⊆V with |T| even, or (ii) ℱ is the set of two-commodity cuts ofG, i.e. cuts separating any two distinguished pairs of vertices ofG, or (iii) ℱ is the set of cuts induced (in a sense) by a ring of subsets of a setT⊆V. In the present work we consider a large class of families of cuts of complete graphs and prove that a family from this class
has the MFMC-property if and only if it is one of (i), (ii), (iii). |
| |
Keywords: | 68 E 10 05 C 99 |
本文献已被 SpringerLink 等数据库收录! |
|