论文标题
在树木上的跳跃数量
On the arboreal jump number of a poset
论文作者
论文摘要
跳跃是一对连续元素，在原始poset中无与伦比的poset扩展中。树木跳跃数是一个NP硬化问题，旨在找到最少跳跃数量的给定Poset的树木延伸。本文的贡献是双重的：（i）〜一个表征，揭示了树木秩序扩展的跳跃数量与其元素分区的大小之间的关系，以满足覆盖图的某些结构特性； （ii）〜一个紧凑的整数编程模型和一种启发式方法，用于解决树木跳跃数问题以及比较这两种策略的计算结果。确切的方法为41个实例中的18个实例提供了最佳证书，执行时间限制为两个小时。此外，我们的启发式方法能够在不到三分钟的时间内找到所有实例的可行解决方案。
A jump is a pair of consecutive elements in an extension of a poset which are incomparable in the original poset. The arboreal jump number is an NP-hard problem that aims to find an arboreal extension of a given poset with minimum number of jumps. The contribution of this paper is twofold: (i)~a characterization that reveals a relation between the number of jumps of an arboreal order extension and the size of a partition of its elements that satisfy some structural properties of the covering graph; (ii)~a compact integer programming model and a heuristic to solve the arboreal jump number problem along with computational results comparing both strategies. The exact method provides an optimality certificate for 18 out of 41 instances with execution time limited to two hours. Furthermore, our heuristic was able to find good feasible solutions for all instances in less than three minutes.
