• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Bai, Bo (Bai, Bo.) [1] | Chen, Xiang (Chen, Xiang.) [2] | Hou, Jian-Feng (Hou, Jian-Feng.) [3] (Scholars:侯建锋) | Zhang, Gong (Zhang, Gong.) [4]

Indexed by:

ESCI CSCD

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:

Min-cut Partition Probabilistic method Random graph Ratio cut

Community:

  • [ 1 ] [Bai, Bo]Huawei Tech Investment Co Ltd, Theory Lab HK, Hong Kong, Peoples R China
  • [ 2 ] [Chen, Xiang]Huawei Tech Investment Co Ltd, Theory Lab HK, Hong Kong, Peoples R China
  • [ 3 ] [Zhang, Gong]Huawei Tech Investment Co Ltd, Theory Lab HK, Hong Kong, Peoples R China
  • [ 4 ] [Hou, Jian-Feng]Fuzhou Univ, Ctr Discrete Math, Fujian 350116, Peoples R China

Reprint 's Address:

Show more details

Related Keywords:

Related Article:

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

Online/Total:122/10136772
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1