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) with a set of terminals K⊂V, a mimicking network is a smaller graph H=(VH,EH) which contains the set of terminals K and for every bipartition U,K−U] of the terminals, the cost of the minimum cut separating U from K−U in G is exactly equal to the cost of the minimum cut separating U from K−U in H. |
| |
Keywords: | Algorithms Analysis of algorithms Approximation algorithms Combinatorial problems Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|