This paper addresses the minimum weight edge cover problem (MEC), which is stated as follows: Given a graph <i>G= (V,E)</i>, find a set of edges <i>S:S⊆E </i>and ∑<sub>e∈S</sub><sup>w(e) </sup></∑<sub>e∈Q<sup>w(e)</sup>∀Q: Q is an edge cover. Where an edge cover <i>P</i> is a set of edges such that ∀v∈V <i>v</i> is incident to at least one edge in <i>P</i>. 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.<br>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/12126774 |
| Date | 17 April 2020 |
| Creators | Steven Alec Gallagher (8708778) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/A_4_3-approximation_for_Minimum_Weight_Edge_Cover/12126774 |
Page generated in 0.0023 seconds