首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 someTV 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 setTV. 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号