Improved Complexity Bound of Vertex Cover for Low degree Graph

Details Improved Complexity Bound of Vertex Cover for Low degree Graph Improved Complexity Bound of Vertex Cover for Low degree Graph

2010-10-14

arxiv.org/abs/1010.2833v1

Computer Science

Data Structures and Algorithms

17 pages

Scientific paper

In this paper, we use a new method to decrease the parameterized complexity bound for finding the minimum vertex cover of connected max-degree-3 undirected graphs. The key operation of this method is reduction of the size of a particular subset of edges which we introduce in this paper and is called as "real-cycle" subset. Using "real-cycle" reductions alone we compute a complexity bound $O(1.15855^k)$ where $k$ is size of the optimal vertex cover. Combined with other techniques, the complexity bound can be further improved to be $O(1.1504^k)$. This is currently the best complexity bound.

Affiliated with

Also associated with

No associations

Rating

Improved Complexity Bound of Vertex Cover for Low degree Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Complexity Bound of Vertex Cover for Low degree Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Complexity Bound of Vertex Cover for Low degree Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-285120