论文标题
一个整数程序和新的下限用于计算图形的强彩虹连接数量
An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs
论文作者
论文摘要
我们提出了一个整数编程模型，以计算任何简单的图形$ g $的强彩虹连接编号，$ src（g）$。我们向提出的模型介绍了几种增强功能，包括快速启发式和可变消除方案。此外，我们为$ src（g）$提出了一种新颖的下限，这可能具有独立的研究兴趣。我们直接解决了整数程序，并使用基于迭代下限改进的替代方法来解决，后者在实践中表现出非常有效的方法。据我们所知，这些是强烈彩虹连接问题的第一个计算方法。我们通过计算包含高达$ 379 $顶点的图形的强彩虹连接数量来证明我们方法的功效。
We present an integer programming model to compute the strong rainbow connection number, $src(G)$, of any simple graph $G$. We introduce several enhancements to the proposed model, including a fast heuristic, and a variable elimination scheme. Moreover, we present a novel lower bound for $src(G)$ which may be of independent research interest. We solve the integer program both directly and using an alternative method based on iterative lower bound improvement, the latter of which we show to be highly effective in practice. To our knowledge, these are the first computational methods for the strong rainbow connection problem. We demonstrate the efficacy of our methods by computing the strong rainbow connection numbers of graphs containing up to $379$ vertices.
