Algorithms For Some Combinatorial Optimization Problems

In a Combinatorial Optimization Problem, one is required to find an element in afinite set such that the objective function on this element is minimum or maximum. Manycombinatorial optimization problems are NP-hard. Three problems are considered in thisthesis. In Chapter2, we find a circle in a3-connected3-regular graph G of length at least|G|rby construction, where r≈0.8is the real root of8.956r+1.036r=10.992r. Thisresult improves the previous work of Jackson [40] in which r≈0.753.In Chapter3and Chapter4, dominating set problems are considered. Let G be agraph, a vertex subset D of G is said to be a connected dominating set of G, if everyvertex of G D has at least one neighbor in D and G[D], the subgraph induced by D,is connected. A connected dominating set D is called an αMOC-CDS if for any vertexu, v of G, there is an (u, v)-path of G whose internal vertices lie in D and whose lengthis at most α times the length of the shortest (u, v)-path in G. In [21], Du et. al. gavea constant factor approximation algorithm on unit disk graph for the case α≥5. InChapter3, we consider the case α <5and give two approximation algorithms on unitdisk graphs. The first one is a constant factor approximation algorithm. The second oneis a polynomial time approximation scheme based on the first one.Let D be a connected dominating set of G. If for any vertex u of G D, there are atleast k vertices in D which are at most r hops away from u, then D is called a connectedr-hop k-dominating set, or (k, r)-CDS for short. In Chapter4, Two approximation al-gorithms for (k, r)-CDS problem are presented. The first one is a two-step algorithm onunit disk graphs whose approximation ratio only depends on k and r. The second oneis a greedy algorithm on general graphs whose approximation ratio is2rH(r+k r),where H(·) is harmonic function, ris the maximum degree in the power graph Gr.