Semester

Fall

Date of Graduation

2019

Document Type

Thesis

Degree Type

MS

College

Statler College of Engineering and Mineral Resources

Department

Lane Department of Computer Science and Electrical Engineering

Committee Chair

K. Subramani

Committee Member

Elaine Eschen

Committee Member

Vahan Mkrtchyan

Abstract

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 a tree T = (V, E), each vertex is associated with a cost c: V →N, each edge with a profit given by p: E → N, and a constraint budget B ≥ 0. The goal of BMVCT is to find the subset of vertices with total cost sum ≤ B such that the total profit 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 [1]. 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 [1].

[1] 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 Steffen, Christel Baier, Mark van den Brand, Johann Eder, Mike Hinchey, and Tiziana Margaria, Eds., Cham, 2017, pp. 350–360, Springer International Publishing.

Download

Share

COinS