The minimum vertex cover is a classical, NP-hard, optimization problem whose objective, given a graph, is to identify the smallest subset of vertices that covers all edges. This paper introduces a decentralized, iterative, and message-passing algorithm that leverages the local knowledge of nodes to resolve the minimum vertex cover. Due to its convergence speed and minimal computational footprint, it also performed well as an in-memory sequential solver, achieving results comparable to those obtained from a state-of-the-art centralized approach.
A Decentralized Strategy for Unweighted Minimum Vertex Cover
Dazzi, Patrizio
2025-01-01
Abstract
The minimum vertex cover is a classical, NP-hard, optimization problem whose objective, given a graph, is to identify the smallest subset of vertices that covers all edges. This paper introduces a decentralized, iterative, and message-passing algorithm that leverages the local knowledge of nodes to resolve the minimum vertex cover. Due to its convergence speed and minimal computational footprint, it also performed well as an in-memory sequential solver, achieving results comparable to those obtained from a state-of-the-art centralized approach.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
