论文标题
最长诱导路径问题的ILP制剂的实验研究
An Experimental Study of ILP Formulations for the Longest Induced Path Problem
论文作者
论文摘要
给定图形$ g =（v，e）$，最长的诱导路径问题要求最大的基数节点子集$ w \ subseteq v $，以使$ w $诱导的图是一条路径。在网络分析中，这是一个长期以来的问题。我们建议针对该问题的新型整数线性编程（ILP）公式，并讨论其有效的实现。将它们与文献中的已知配方进行比较，我们证明它们在理论上是有益的，可以产生更强的放松。此外，我们的实验表明了它们的实际优势。
Given a graph $G=(V,E)$, the longest induced path problem asks for a maximum cardinality node subset $W\subseteq V$ such that the graph induced by $W$ is a path. It is a long established problem with applications, e.g., in network analysis. We propose novel integer linear programming (ILP) formulations for the problem and discuss efficient implementations thereof. Comparing them with known formulations from literature, we prove that they are beneficial in theory, yielding stronger relaxations. Moreover, our experiments show their practical superiority.
