EUVIMEDEUVIMED entdecken
Crossref

An Approximate Solution to the Minimum Vertex Cover Problem: The Hvala Algorithm

Frank Vega

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →