论文标题
计算导向的施泰纳路径盖
Computing Directed Steiner Path Covers
论文作者
论文摘要
在本文中，我们考虑了定向的共同行为的定向施泰纳路径覆盖问题。给定一个有向图的G =（V，E）和所谓的V的V v的子集T，问题是要找到最少数量的顶点 - 偶发性简单的直接路径，这些路径包含所有终端顶点和最少数量的非终端顶点（Steiner Vertices）。主要最小化标准是路径的数量。我们展示了如何在线性时间计算有针对性的涂层的最小施材路径盖。如果存在，这会导致对有向共插图的最佳定向施材路径的线性时间计算。由于Steiner路径问题概括了Hamiltonian路径问题，因此我们的结果暗示了定向共同行为的Hamiltonian Path问题的第一种线性时间算法。我们还为（定向的）汉密尔顿路径问题，（定向的）施泰纳路径问题以及（定向的）Steiner路径覆盖问题提供了二进制整数程序。这些整数程序可用于最大程度地减少公司在电子行业中使用的采摘机器中的更换时间。
In this article we consider the Directed Steiner Path Cover problem on directed co-graphs. Given a directed graph G=(V,E) and a subset T of V of so-called terminal vertices, the problem is to find a minimum number of vertex-disjoint simple directed paths, which contain all terminal vertices and a minimum number of non-terminal vertices (Steiner vertices). The primary minimization criteria is the number of paths. We show how to compute in linear time a minimum Steiner path cover for directed co-graphs. This leads to a linear time computation of an optimal directed Steiner path on directed co-graphs, if it exists. Since the Steiner path problem generalizes the Hamiltonian path problem, our results imply the first linear time algorithm for the directed Hamiltonian path problem on directed co-graphs. We also give binary integer programs for the (directed) Hamiltonian path problem, for the (directed) Steiner path problem, and for the (directed) Steiner path cover problem. These integer programs can be used to minimize change-over times in pick-and-place machines used by companies in electronic industry.
