## Graduate Theses, Dissertations, and Problem Reports

### An Empirical Analysis of an Algorithm for the Budgeted Maximum Vertex Cover Problem in Trees

Fall

2019

Thesis

MS

#### College

Statler College of Engineering and Mineral Resources

#### Department

Lane Department of Computer Science and Electrical Engineering

K. Subramani

Elaine Eschen

Vahan Mkrtchyan

#### Abstract

Covering problems are commonly studied in ﬁelds 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 ﬁnding the Budgeted Maximum Vertex Cover in undirected trees (BMVCT). The BMVCT problem is deﬁned as follows: Given a tree T = (V, E), each vertex is associated with a cost c: V →N, each edge with a proﬁt given by p: E → N, and a constraint budget B ≥ 0. The goal of BMVCT is to ﬁnd the subset of vertices with total cost sum ≤ B such that the total proﬁt of the covered edges is maximized. The BMVCT problem occurs in a number of domains such as in transportation or building network base stations and can be adapted to solve the partial vertex cover problem. In particular, we implement the algorithm in . We test the implementation with star trees, random trees, and binary trees. This implementation can be adapted to solve the weighted partial vertex cover on trees (WPVCT) as discussed in .

 Vahan Mkrtchyan, Ojas Parekh, Danny Segev, and K. Subramani, “The approximability of partial vertex covers in trees,” in SOFSEM 2017: Theory and Practice of Computer Science, Bernhard Steﬀen, Christel Baier, Mark van den Brand, Johann Eder, Mike Hinchey, and Tiziana Margaria, Eds., Cham, 2017, pp. 350–360, Springer International Publishing.

COinS

#### DOI

https://doi.org/10.33915/etd.7407