TY - JOUR

T1 - Partitioning a multi-weighted graph to connected subgraphs of almost uniform size

AU - Ito, Takehiro

AU - Goto, Kazuya

AU - Zhou, Xiao

AU - Nishizeki, Takao

PY - 2007/2

Y1 - 2007/2

N2 - Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers l i and ui, 1 ≤ i ≤ q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤ i ≤ q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees, that is, graphs with bounded tree-width.

AB - Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers l i and ui, 1 ≤ i ≤ q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤ i ≤ q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees, that is, graphs with bounded tree-width.

KW - Algorithm

KW - Choice partition

KW - Lower bound

KW - Maximum partition problem

KW - Minimum partition problem

KW - Multi-weighted graph

KW - Partial k-tree

KW - Series-parallel graph

KW - Uniform partition

KW - Upper bound

UR - http://www.scopus.com/inward/record.url?scp=33847093306&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847093306&partnerID=8YFLogxK

U2 - 10.1093/ietisy/e90-d.2.449

DO - 10.1093/ietisy/e90-d.2.449

M3 - Article

AN - SCOPUS:33847093306

VL - E90-D

SP - 449

EP - 456

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

SN - 0916-8532

IS - 2

ER -