论文标题
连接的顶点覆盖问题的确切方法
Exact approaches for the Connected Vertex Cover problem
论文作者
论文摘要
给定图形$ g $，连接的顶点覆盖问题（CVC）要求找到$ g $的最低基数顶点盖，以诱导连接的子图。在本文中，我们描述了一些解决CVC问题的方法。首先，我们为CVC提供紧凑的混合构造的扩展配方：这些是针对此问题提出的第一个配方，可以很容易地适应问题的变化，例如树覆盖。其次，我们描述了CVC问题的简单分支和界限算法。最后，我们实施算法并将其性能与我们的最佳表述进行比较：与经典顶点覆盖问题通常发生的情况相反，我们的配方表现优于分支和界限算法。
Given a graph $G$, the Connected Vertex Cover problem (CVC) asks to find a minimum cardinality vertex cover of $G$ that induces a connected subgraph. In this paper we describe some approaches to solve the CVC problem exactly. First, we give compact mixed-integer extended formulations for CVC: these are the first formulations proposed for this problem, and can be easily adapted to variations of the problem such as Tree Cover. Second, we describe a simple branch and bound algorithm for the CVC problem. Finally, we implement our algorithm and compare its performance against our best formulation: contrary to what usually happens for the classical Vertex Cover problem, our formulation outperforms the branch and bound algorithm.
