Indexed by:
Abstract:
Let G be a graph and ( V-1, V-2, center dot center dot center dot, Vk) be a k-partition of G. For 1 <= i < j <= k, the ratio of (V-i, V-j), denoted by R(V-i, V-j), is e(V-i, V-j)/(|V-i ||V-j |), where e( V-i, V-j) is the number of crossing edges. The minimum k-ratio of G, denoted by R-k(G), is the minimum Sigma(1 <= i< j <= k) R(V-i, V-j) over all k-partitions ( V-1, V-2, center dot center dot center dot, Vk) of G. Let R(G) = R-2(G). The ratio cut problem, posed by Wei and Cheng, and independently by Leighton and Rao, is an extension of the min-cut problem and has important applications in CAD. It is easy to see that Rk (G) is closely related to the density d(G) of a graph G. In this paper, we mainly give some results on R-k(G) with respect to d(G). First, we show that R-k(G) <= ((k)(2))(1 + o(1))d(G) for graphs G and R-k(G)<= ( k - 1)(1+ o(1))d( G) for sparse graphs G. Then, we give some upper and lower bounds on R(G). In particular, we show R( G) <= 4/(n - 3) for every planar graph G with n >= 4 vertices. At last, we consider the random graph G(n, p) and show that R(G(n, p)) can be determined asymptotically almost surely if p >= C log n/n for some constant C > 0.
Keyword:
Reprint 's Address:
Source :
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA
ISSN: 2194-668X
Year: 2023
0 . 9
JCR@2023
0 . 9 0 0
JCR@2023
JCR Journal Grade:4
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: