标题： Steiner路径聚合问题 显示英文标题

标题： The Steiner Path Aggregation Problem

摘要： 在Steiner路径聚合问题中，我们的目标是将有向网络中的路径聚合到一个单一的树状结构中，而不会显著干扰这些路径。 特别是，我们给定一个带有颜色弧的有向多重图、一个根节点和$k$个终端，每个终端都有一条单色路径到达根节点。 我们的目标是找到一个树状结构，其中每个终端都有一条到达根节点的路径，且其路径的颜色切换次数不会太多。 我们给出一个高效的算法，可以找到一种最多具有$2\log_{4/3}k$次颜色切换的解决方案。 考虑到常数因子，这是可能的最佳普遍界限，因为存在至少需要$\log_2 k$次颜色切换的图。 显示英文摘要

摘要： In the Steiner Path Aggregation Problem, our goal is to aggregate paths in a directed network into a single arborescence without significantly disrupting the paths. In particular, we are given a directed multigraph with colored arcs, a root, and $k$ terminals, each of which has a monochromatic path to the root. Our goal is to find an arborescence in which every terminal has a path to the root, and its path does not switch colors too many times. We give an efficient algorithm that finds such a solution with at most $2\log_{4/3}k$ color switches. Up to constant factors this is the best possible universal bound, as there are graphs requiring at least $\log_2 k$ color switches.