FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS
Bang Ye Wu · Discrete Mathematics Algorithms and Applications · 2012
We study how to partition an interval graph with non-negative vertex weights into k connected subgraphs such that the minimum total weight of any part of the partition is maximized. For k = 2, it is shown that for any ε > 0, a (1 + ε)-approximation can be found in O((1/ε)n3) time, i.e., it admits a fully polynomial-time approximation scheme (FPTAS). For any fixed k > 2, the problem also admits an FPTAS when restricted to k-connected interval graphs.