2022/07/19 by Rodrigo A. Castro, José Miguel Díaz-Báñez, Castro, Rodrigo A. +9
Computer Science · #05C70 (Primary) #68W25 (Secondary) #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2207.09063
openalex publication_date 2022/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G=(V,E) with costs on its edges, the minimum-cost edge cover problem consists of finding a subset of E covering all vertices in V at minimum cost. If G is bipartite, this problem can be solved in time O(|V|3) via a well-known reduction to a maximum-cost matching problem on G. If in addition V is a set of points on the Euclidean line, Collanino et al. showed that the problem can be solved in time O(|V| log |V|) and asked whether it can be solved in time o(|V|3) if V is a set of points on the Euclidean plane. We answer this in the affirmative, giving an O(|V|2.5 log |V|) algorithm based on the Hungarian method using weighted Voronoi diagrams. We also propose some 2-approximation algorithms and give experimental results of our implementations.