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


On mimicking networks representing minimum terminal cuts
Authors:Arindam Khan  Prasad Raghavendra
Affiliation:1. School of Computer Science, Georgia Institute of Technology, Atlanta, USA;2. Electrical Engineering and Computer Sciences, University of California, Berkeley, USA
Abstract:Given a capacitated undirected graph G=(V,E)G=(V,E) with a set of terminals K⊂VKV, a mimicking network   is a smaller graph H=(VH,EH)H=(VH,EH) which contains the set of terminals K   and for every bipartition U,K−U]U,KU] of the terminals, the cost of the minimum cut separating U   from K−UKU in G is exactly equal to the cost of the minimum cut separating U   from K−UKU in H.
Keywords:Algorithms  Analysis of algorithms  Approximation algorithms  Combinatorial problems  Graph algorithms
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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