Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
复制标题
DOI：
10.1016/j.dam.2008.08.002
复制
发表时间：
2009-02
期刊：
影响因子：
--
通讯作者：
Siamak Tazari;M. Müller-Hannemann
中科院分区：
文献类型：
--
作者：
Siamak Tazari;M. Müller-Hannemann
我们推广了Henzinger等人（1994）的具有非负边权的平面图的线性时间最短路算法，使其适用于任何适当的小闭图类。我们认为，他们的算法不能适应所有适当的小封闭类的标准方法。利用图子式理论中最近的一些深入结果，我们给出了如何在线性时间内为除固定子式之外的任何图构造一个适当的递归除法，以及如何在之后变换图及其除法，使其具有最大度3.基于这样的划分，可以应用Henzinger等人的原始框架。然后，我们证明了使用这个算法，可以在线性时间内在这些图类上实现Mehlhorn（1988）的Steiner树问题的2-近似算法。
We generalize the linear-time shortest-paths algorithm for planar graphs with nonnegative edge-weights of Henzinger et al. (1994) to work for any proper minor-closed class of graphs. We argue that their algorithm can not be adapted by standard methods to all proper minor-closed classes. By using recent deep results in graph minor theory, we show how to construct an appropriate recursive division in linear time for any graph excluding a fixed minor and how to transform the graph and its division afterwards, so that it has maximum degree three. Based on such a division, the original framework of Henzinger et al. can be applied. Afterwards, we show that using this algorithm, one can implement Mehlhorn’s (1988) 2-approximation algorithm for the Steiner tree problem in linear time on these graph classes.