For a connected graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$G=(V,E)$$</EquationSource> </InlineEquation> and a positive integral vertex weight function <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$w$$</EquationSource> </InlineEquation>, a max-min weight balanced connected <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$k$$</EquationSource> </InlineEquation>-partition of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$G$$</EquationSource> </InlineEquation>, denoted as <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$BCP_k$$</EquationSource> </InlineEquation>, is a partition of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$V$$</EquationSource> </InlineEquation> into <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$$k$$</EquationSource> </InlineEquation> disjoint vertex subsets <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$$(V_1,V_2,\ldots ,V_k)$$</EquationSource> </InlineEquation> such that each <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$$G[V_i]$$</EquationSource> </InlineEquation> (the subgraph of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$$G$$</EquationSource> </InlineEquation> induced by <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$$V_i$$</EquationSource> </InlineEquation>) is connected, and <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$$\min _{1\le i\le k}\{w(V_i)\}$$</EquationSource> </InlineEquation> is maximum. Such a problem has a lot of applications in image processing and clustering, and was proved to be NP-hard. In this paper, we study <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$$BCP_k$$</EquationSource> </InlineEquation> on a special class of graphs: trapezoid graphs whose maximum degree is bounded by a constant. A pseudo-polynomial time algorithm is given, based on which an FPTAS is obtained for <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$$k=2,3,4$$</EquationSource> </InlineEquation>. A step-stone for the analysis of the FPTAS depends on a lower bound for the optimal value of <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$$BCP_k$$</EquationSource> </InlineEquation> in terms of the total weight of the graph. In providing such a lower bound, a byproduct of this paper is that any 4-connected trapezoid graph on at least seven vertices has a 4-contractible edge, which may have a value in its own right. Copyright Springer Science+Business Media New York 2013
