论文标题
欧几里得双方边缘盖问题的算法
Algorithms for the Euclidean Bipartite Edge Cover Problem
论文作者
论文摘要
给定图形$ g =（v，e）$，其边缘成本，最低成本的边缘盖问题包括在$ e $ v $中以最低成本查找$ e $的子集。如果$ g $是双方的，则可以通过众所周知的减少到$ g $上的最大成本匹配问题来在时间$ o（| v |^3）$中解决此问题。如果另外$ v $是欧几里得线上的一组点，Collanino等人。表明问题可以在时间$ o（| v | \ log | v |）$中解决，并询问是否可以在时间$ o（| v |^3）$中解决问题，如果$ v $是欧几里得平面上的一组点。我们以肯定的方式回答了这一点，给出了$ o（| v |^{2.5} \ log | v |）$算法，基于匈牙利方法，使用加权Voronoi图。我们还提出了一些两种2个附属算法，并给出实施的实验结果。
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.
