Partitioning Of Connected Subgraphs In Vertex-weighted Graph

Graph partition is one of the most fundamental problems in the field of graph theory and network optimization.This thesis mainly studies the connected subgraph partition problem(referred to as k-GP)in the vertex-weighted connected graph:given a simple vertex-weighted undirected connected graph G=(V,E)and an integer k?2,our problem is to divide the vertex set V into k non-empty subsets,such that the derived subgraph of each vertex subset is connected,and the goal is to minimize the maximum subset of weights.The main content of this paper is to design polynomial time approximation algorithms to solve this problem,and theoretically prove its worst-case ratio of the algorithm.The full thesis is divided into five chapters to elaborate.The first chapter first introduces the combination optimization problem and computational complexity theory,and describes the basic concepts such as the approximation algorithm and the worst-case ratio.Then we introduce the basic knowledge of graph theory,and also introduce the problem of connected subgraph partitioning in the edge-weighted graph which is closely related to the problem studied in this paper.We point out the difference and connection between the problem and the connected subgraph partition problem in the vertex-weighted graph studied in this paper.Finally,the domestic and international research status of connected subgraph partitioning problem is reviewed.The second chapter studies the 2-GP problem,that is,the vertex set V of the vertex-weighted undirected connected graph is divided into two non-empty subsets.The derived sub-graph G(Vi)of each subset Vi(1?i?2)is connected,and the target makes the total weight of the larger subset of vertex weights as small as possible.A polynomial time approximation algorithm with a worst case bound of 4/3 is designed for this problem,and an example is provided to show that the bound is tight.The third chapter studies the 3-GP problem,that is,the vertex set V of the vertex-weighted undirected connected graph is divided into three non-empty subsets.The derived sub-graph G(Vi)of each subset Vi(1?i?3)is connected,and the target makes the total weight of the larger subset of vertex weights as small as possible.A polynomial time approximation algorithm with a worst case bound of 3/2 is designed for this problem,and an example is provided to show that the bound is tight.In particular,the worst-case analysis of the algorithm for this problem is more complicated.The fourth chapter studies the general case of k-GP,which divides the vertex set V of the undirected connected graph of vertex weighting into k non-empty subsets.The derived subgraph G(Vi)of each subset Vi(1?i?k)is connected,and the target makes the total weight of the larger subset of vertex weights as small as possible.Based on the algorithm design and analysis of 3-GP problem,we design a polynomial time approximation algorithm with the worst-case bound k/2.The fifth chapter summarizes the article and gives the future research direction.