| Popis: |
Given a capacitated undirected graph G=(V,E) with a set of terminals [email protected]?V, a mimicking network is a smaller graph H=(V"H,E"H) 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. In this work, we improve both the previous known upper bound of 2^2^^^k[1] and lower bound of (k+1)[2] for mimicking networks, reducing the doubly-exponential gap between them to a single-exponential gap as follows:*Given a graph G, we exhibit a construction of mimicking network with at most k'th Hosten-Morris number (~2^(^(^k^-^1^)^@?^(^k^-^1^)^/^2^@?^)) of vertices (independent of the size of V). *There exist graphs with k terminals that have no mimicking network with less than 2^k^-^1^2 number of vertices. |
Full Text from ScienceDirect