论文标题
多目标跨度问题的复杂性
Complexity of the Multiobjective Spanner Problem
论文作者
论文摘要
在本文中，我们深入探讨了迄今未探索的多目标跨度（MSP）问题的复杂性。 MSP是对良好的最小T-Spanner问题的多目标概括。这种多目标方法使我们能够找到在成本和公用事业之间提供可行折衷的解决方案。因此，当涉及基础架构的计划时，MSP可以是强大的建模工具。我们表明，对于第三级有限的外平面实例，MSP是棘手的，计算非主导的集合是buco-hard。此外，我们证明，如果p！= np，对于具有单位成本和任意图的实例，则不能在输出多项式时间内计算非主导的集合和极端点集。此外，我们考虑上述案例的定向版本。
In this paper, we take an in-depth look at the complexity of a hitherto unexplored Multiobjective Spanner (MSp) problem. The MSp is a multiobjective generalization of the well-studied Minimum t-Spanner problem. This multiobjective approach allows us to find solutions that offer a viable compromise between cost and utility. Thus, the MSp can be a powerful modeling tool when it comes to the planning of, e.g., infrastructure. We show that for degree-3 bounded outerplanar instances the MSp is intractable and computing the non-dominated set is BUCO-hard. Additionally, we prove that if P != NP, neither the non-dominated set nor the set of extreme points can be computed in output-polynomial time, for instances with unit costs and arbitrary graphs. Furthermore, we consider the directed versions of the cases above.
