论文标题
在可探索的边缘和顶点不确定性下的最小跨越树问题的特殊情况
Special Cases of the Minimum Spanning Tree Problem under Explorable Edge and Vertex Uncertainty
论文作者
论文摘要
本文研究了该问题的最小跨越树问题以及相关的顶点不确定性版本。我们特别考虑了我们提供随机算法的特殊实例类型，包括仙人掌图。我们介绍了在不确定性下找到最小重量跨度恒星的问题，我们表明没有算法可以达到恒定的竞争比率。
This article studies the Minimum Spanning Tree Problem under Explorable Uncertainty as well as a related vertex uncertainty version of the problem. We particularly consider special instance types, including cactus graphs, for which we provide randomized algorithms. We introduce the problem of finding a minimum weight spanning star under uncertainty for which we show that no algorithm can achieve constant competitive ratio.
