On The Characterization Of Mengerian Graphs And Efficient Algorithms

The research on packing and covering problems play a very important role in the development of combinatorial optimization,a branch of mathematics.For a given graph,a set of edges with no two of them sharing a common vertex is called a matching and a set of vertices that collectively incident with all edges in the graph is called a vertex cover.Based on these two concepts,two important optimization problems—the maximum matching problem(which is in P)and the minimum vertex cover problem(which is in NP)—has greatly promoted the development of combinatorial optimization.The classical K¨onig's theorem asserts that the maximum cardinality of matching equals the minimum cardinality of a vertex cover in bipartite graphs.In this dissertation,we consider the generalized form of the K¨onig's theorem,explore the relationship between the maximum edge packing problem and the minimum(weighted)vertex cover problem,design efficient algorithms for solving them on bipartite graphs and characterize the structures such that these two optimization problems have the same optimum value for any given nonnegative weights putting on vertices.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 with the help of the notion of edge packing.Actually,we show that the maximum cardinality of an edge packing always equals the minimum total weight of a vertex cover in bipartite graphs.Our maxmin theorem generalizes the K¨onig's theorem.We also design efficient algorithms for solving the maximum edge packing problem and the minimum weighted vertex cover problem in bipartite graphs.Finally,we characterize the underlying structures such that the maximum cardinality of an edge packing equals to the minimum total weight of a vertex cover for any nonnegative integral weight function defined on the vertex set of the graph.Our results may have potential use in tackling some similar packing or covering problems in the future.