An Approximate Solution to the Minimum Vertex Cover Problem: The Hvala Algorithm
Gauge Freedom Journal · 2026 · 1 (1)
DOI: 10.65323/gfj.2026.004 ↗Kurz gefasst
Fachartikel in der Zeitschrift Gauge Freedom Journal, 2026. Verfasst von Frank Vega.
Abstract (Originalsprache)
We present \textbf{Hvala}, a linear-time ensemble approximation algorithm for Minimum Vertex Cover that combines a maximal-matching 2-approximation, a bucket-queue maximum-degree greedy, and the degree-$1$ weighted-reduction Hallelujah heuristic of a companion work, applies redundant-vertex pruning to each, and returns the smallest of the four resulting covers. We prove unconditionally that Hvala runs in $\mathcal{O}(n+m)$ time and space and attains worst-case approximation ratio $\rho\le 2$ on every finite simple graph; conditional on the strict pointwise inequality of the Hallelujah heuristic, the bound improves to $|S|
Zitieren
APA
Vega, F. (2026). An Approximate Solution to the Minimum Vertex Cover Problem: The Hvala Algorithm. Gauge Freedom Journal, 1(1). https://doi.org/10.65323/gfj.2026.004
Vancouver
Vega F. An Approximate Solution to the Minimum Vertex Cover Problem: The Hvala Algorithm. Gauge Freedom Journal. 2026;1(1). doi:10.65323/gfj.2026.004
BibTeX
@article{Vega2026,
author = {Vega, Frank},
title = {An Approximate Solution to the Minimum Vertex Cover Problem: The Hvala Algorithm},
journal = {Gauge Freedom Journal},
year = {2026},
volume = {1},
number = {1},
doi = {10.65323/gfj.2026.004}
}
EUVIMED