A Fast-Converging Decentralized Approach to the Weighted Minimum Vertex Cover Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914090712039424 |
|---|---|
| author | Mordacchini, Matteo Carlini, Emanuele Dazzi, Patrizio |
| author_facet | Mordacchini, Matteo Carlini, Emanuele Dazzi, Patrizio |
| contents | We address the problem of computing a Minimum Weighted Vertex Cover (MWVC) in a decentralized network. MWVC, a classical NP-hard problem, is foundational in applications such as network monitoring and resource placement. We propose a fully decentralized protocol where each node makes decisions using only local knowledge and communicates with its neighbors. The method is adaptive, communication-efficient, and avoids centralized coordination. We evaluate the protocol on real-world and synthetic graphs, comparing it to both centralized and decentralized baselines. Our results demonstrate competitive solution quality with reduced communication overhead, highlighting the feasibility of MWVC computation in decentralized environments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_11697 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Fast-Converging Decentralized Approach to the Weighted Minimum Vertex Cover Problem Mordacchini, Matteo Carlini, Emanuele Dazzi, Patrizio Distributed, Parallel, and Cluster Computing Data Structures and Algorithms We address the problem of computing a Minimum Weighted Vertex Cover (MWVC) in a decentralized network. MWVC, a classical NP-hard problem, is foundational in applications such as network monitoring and resource placement. We propose a fully decentralized protocol where each node makes decisions using only local knowledge and communicates with its neighbors. The method is adaptive, communication-efficient, and avoids centralized coordination. We evaluate the protocol on real-world and synthetic graphs, comparing it to both centralized and decentralized baselines. Our results demonstrate competitive solution quality with reduced communication overhead, highlighting the feasibility of MWVC computation in decentralized environments. |
| title | A Fast-Converging Decentralized Approach to the Weighted Minimum Vertex Cover Problem |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.11697 |