论文标题
关于包装时间昂贵的树木
On packing time-respecting arborescences
论文作者
论文摘要
我们对Kamiyama和Kawase \ cite {kamkaw}的结果进行了轻微的概括，该结果{kamkaw}在无循环的pre-flow Pre-Flow时间网络中包装时间探索的arborescences。我们的主要贡献是在非准次时间网络中包装时间昂贵的轴心提供第一个结果。作为负面的结果，我们证明了存在2个弧形 - 偶口的决策问题的NP完整性，这些弧形跨越了时间，并且本文提出了相关的问题。
We present a slight generalization of the result of Kamiyama and Kawase \cite{kamkaw} on packing time-respecting arborescences in acyclic pre-flow temporal networks. Our main contribution is to provide the first results on packing time-respecting arborescences in non-acyclic temporal networks. As negative results, we prove the NP-completeness of the decision problem of the existence of 2 arc-disjoint spanning time-respecting arborescences and of a related problem proposed in this paper.
