The Study On Algorithms Design And Complexity For Edge Packing Problems

The minimum vertex cover problem is a classical combinatorial optimization prob-lem.While the minimum(weighted)vertex cover problem is a well-known NP-hard problem in general graphs,it can be solved efficiently in bipartite graphs.To solve the minimum(weighted)vertex cover problem on bipartite graphs,we can consider the edge packing problem by using the special structure of bipartite graphs.The edge packing problem in graphs not only can be considered as a generalization of the match-ing problem,but also happen to be the duality of the minimum(weighted)vertex cover problem in graphs.In this dissertation,we describe the edge packing problem formally,study and analyse the time complexity of the algorithm about solving the edge packing problem in graphs.Given a graph G=(V;E;w)such that each vertex v ? V is as-sociated with a positive integer w(v),an edge packing F with respect to these integers(abbreviated as edge packing)is a collection of edges(repetition is allowed)of G such that each vertex(counting multiplicities)v belongs to at most w(v)members of F.The maximum edge packing problem asks for an edge packing containing edges as many as possible.In this dissertation,firstly,the polynomial time solvability of the maximum edge packing problem with vertex weighted general graphs is described,and an algorithm in polynomial time to solve the edge packing problem in graphs is designed.This algorithm runs in O((|E|+|V|log|V|)(|V|2 log |V|)).An algorithm in(?)to solve the edge packing problem in graphs with vertex weighted being 2 is presented.Secondly,the time complexity of the algorithm is improved to(?)for the maximum edge packing problem with vertex weighted bipartite graphs.Finally,a new proof of a 2-approximation algorithm for solving vertex cover problem on general graphs is given by using the combinatorial property of maximal edge packing.