Class Year

2017

Document Type

Thesis

Honors Designation

High Honors

Department

Computer Science

Primary Advisor

Darren Strash

Abstract

The Minimum Vertex Cover problem asks us to find a minimum set of vertices in a graph such that each edge of the graph is incident to at least one vertex of the set. It is a classical NP-hard problem and in the past researchers have suggested both exact algorithms and heuristic approaches to tackle the problem. In this thesis, we improve Akiba and Iwata’s branch-and-reduce algorithm, which is one of the fastest exact algorithms in the field, by developing three techniques: dependency checking, caching solutions and feeding an initial high quality solution to accelerate the algorithm’s performance. We are able to achieve speedups of up to 3.5 on graphs where the algorithm of Akiba and Iwata is slow. On one such graph, the Stanford web graph, our techniques are especially effective, reducing the runtime from 16 hours to only 4.6 hours.

Share

COinS