MEM_APPROX.pdf (231.97 kB)
Download file

A 4/3-approximation for Minimum Weight Edge Cover

Download (231.97 kB)
thesis
posted on 2020-04-17, 02:07 authored by Steven Alec GallagherSteven Alec Gallagher
This paper addresses the minimum weight edge cover problem (MEC), which is stated as follows: Given a graph G= (V,E), find a set of edges S:S⊆E and ∑e∈Sw(e) e∈Qw(e)∀Q: Q is an edge cover. Where an edge cover P is a set of edges such that ∀v∈V v is incident to at least one edge in P. An efficient implementation of a 4/3-approximation for MEC is provided. Empirical results obtained experimentally from practical data sets are reported and compared against various other approximation algorithms for MEC.

History

Degree Type

Master of Science

Department

Computer Science

Campus location

West Lafayette

Advisor/Supervisor/Committee Chair

Alex Pothen

Additional Committee Member 2

Gustavo Rodriguez-rivera

Additional Committee Member 3

Pedro Fonseca

Usage metrics

Licence

Exports