Engineering Commons^™

An Empirical Analysis Of An Algorithm For The Budgeted Maximum Vertex Cover Problem In Trees, Mujidat Abisola Adeyemo

Graduate Theses, Dissertations, and Problem Reports

Covering problems are commonly studied in fields such as mathematics, computer science, and engineering. They are also applicable in the real world, e.g., given a city, can we build base-stations such that there is network availability everywhere in the city. However, in the real world, there are usually constraints such as cost and resources. The Budgeted Maximum Vertex Cover is a generalization of covering problems. It models situations with constraints. In this thesis, we empirically analyze an algorithm for the problem of finding the Budgeted Maximum Vertex Cover in undirected trees (BMVCT). The BMVCT problem is defined as follows: Given …