论文标题
优先限制的树木
Precedence-Constrained Arborescences
论文作者
论文摘要
在图理论领域中，最低成本的树状问题是一个充分研究的问题，其已知的多项式时间算法用于求解它。先前的文献引入了有关原始问题和/或约束的原始问题的新变化。最近，提出了优先限制的最低成本树木的问题，其中在成对的顶点上实施了优先限制。这些限制阻止了违反树木沿线关系的定向路径的形成。我们表明这个问题是NP-HARD，我们为其引入了一种新的可扩展混合整数线性编程模型。关于以前的模型，新提出的模型的性能要好得多。这项工作还引入了对最低成本的树木抗衡问题的新变化，并具有优先限制。我们表明，这种新的变化也是NP-HARD，我们提出了几种混合整数线性编程模型来制定问题。
The minimum-cost arborescence problem is a well-studied problem in the area of graph theory, with known polynomial-time algorithms for solving it. Previous literature introduced new variations on the original problem with different objective function and/or constraints. Recently, the Precedence-Constrained Minimum-Cost Arborescence problem was proposed, in which precedence constraints are enforced on pairs of vertices. These constraints prevent the formation of directed paths that violate precedence relationships along the tree. We show that this problem is NP-hard, and we introduce a new scalable mixed integer linear programming model for it. With respect to the previous models, the newly proposed model performs substantially better. This work also introduces a new variation on the minimum-cost arborescence problem with precedence constraints. We show that this new variation is also NP-hard, and we propose several mixed integer linear programming models for formulating the problem.
