Maximum Path Sets in Trees

doi:10.1007/978-3-032-09524-4_15

Maximum Path Sets in Trees

2026-01-01

0

PRE

AI

DOI：10.1007/978-3-032-09524-4_15

原文链接

原文求助

摘要

En 中文

本文提出了无向树和有根树中最大路径集（MPS）问题的线性时间算法。在MPS问题中，给定一个图G = (V, E)，要求找到一个最大基数且E'是E的子集的边集E'，使得G' = (V, E')是由顶点不相交路径组成的集合。MPS问题在多个物流领域有应用。在[3]中，已经证明该问题在一般图中是NP完全的。本文证明MPS问题在无向树中可在线性时间内求解。此外，我们将MPS问题约简为bb-匹配问题，后者可进一步约简为最大流问题。从多面体角度，我们设计了树中MPS问题的整数规划模型，并证明该模型的约束矩阵是完全幺模的。换言之，求解线性规划松弛即可得到整数解。我们还设计了线性时间算法以求解有根树中的MPS问题，有根树是一类有向树。最后，我们对该文讨论的各算法进行了实证分析。

Keyword:

Maximum Path Set

Linear time algorithm

Linear Program

Empirical Analysis

Maximum Path Sets in Trees

摘要

期刊

机构

引用论文