Connected Graph Partition Problem With Upper Bound

The maximum bounded connected bipartition problem is a hybrid variant of the maximum balanced connected partition problem on connected graphs in combinatorial optimization and the maximum total early work problem in scheduling theory.It has a wide application background in real life,such as truck loading,crop harvesting,task allocation,etc.Given a vertex-weighted connected graph G=(V,E;w)and an upper bound constant B,where w:V→R≥0 is the weight function of the vertex and B is the upper bound of the weight of each subset.The maximum bounded connected bipartition problem is to partition the vertex set V into two subsets denoted as(Vi,V2)such that both subgraphs induced by Vl and V2 are connected and the total weight of these two subgraphs is maximized,where the weight of the subgraph is the minimum of the sum of the weight of all vertices and B.In Chapter 2,firstly,we consider the maximum bounded connected bipartition problem in biconnected graphs,which using the definition of st numbers to rearrange the vertices in the graph,then we design an approximation algorithm with an approximate ratio of 8/7;Next,because of the structural properties of connected graphs,the block connection tree of graphs is constructed,then we reduce the maximum bounded connected bipartition problem on connected graphs to this problem on biconnected graphs and design an approximation algorithm with an approximate ratio of no more than 8/7.In Chapter 3,firstly,we consider the maximum bounded connected bipartition problem in interval graphs,then based on a dynamic programming algorithm,it is proved that the problem has a full polynomial time approximation;Next,we consider the maximum bounded connected bipartition problem in grid graphs,an approximation algorithm with approximate ratio 14/13 is designed by classifying and discussing the number of vertices in the heavy vertex set.