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

author:

Fan, Genghua (Fan, Genghua.) [1] (Scholars:范更华) | Hou, Jianfeng (Hou, Jianfeng.) [2] (Scholars:侯建锋) | Zeng, Qinghou (Zeng, Qinghou.) [3] (Scholars:曾庆厚)

Indexed by:

EI Scopus SCIE

Abstract:

Judicious Partition Problem is to partition the vertex set of a graph such that certain quantities are optimized simultaneously. Let k be a positive integer and G a graph with in edges. It is proved in this paper that the vertex set of G can be partitioned into k parts V-1, ... V-k such that e(V-i) <= m/k(2) + k-1/2k(2) (root 2m + 1/4 - 1/2) + 2/3 for each i is an element of {1, 2, ..., k} and e(V-1, ..., V-k) >= k-1/km + k-1/2k (root 2m + 1/4 - 1/2) - (k-2)(2)/8k, congruent to where e(V-i) is the number of edges with both ends in V-i and e (V-1, ..., V-k) = m - Sigma(k)(i=1) e(V-i). This partially solves a problem proposed by Bollobas and Scott, and, for some values of m, solves the problem affirmatively. (C) 2014 Elsevier B.V. All rights reserved.

Keyword:

Graph Judicious partition Max-Cut problem Switching

Community:

  • [ 1 ] [Fan, Genghua]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China
  • [ 2 ] [Hou, Jianfeng]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China
  • [ 3 ] [Zeng, Qinghou]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China

Reprint 's Address:

  • 侯建锋

    [Hou, Jianfeng]Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China

Show more details

Version:

Related Keywords:

Related Article:

Source :

DISCRETE APPLIED MATHEMATICS

ISSN: 0166-218X

Year: 2014

Volume: 179

Page: 86-99

0 . 8 0 2

JCR@2014

1 . 0 0 0

JCR@2023

ESI Discipline: ENGINEERING;

ESI HC Threshold:184

JCR Journal Grade:3

CAS Journal Grade:3

Cited Count:

WoS CC Cited Count: 14

SCOPUS Cited Count: 16

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 3

Online/Total:557/10964116
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