Purdue University Graduate School
MEM_APPROX.pdf (231.97 kB)

A 4/3-approximation for Minimum Weight Edge Cover

Download (231.97 kB)
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.


Degree Type

  • Master of Science


  • 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