Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation |
| |
Authors: | Siamak Tazari,Matthias Mü ller-Hannemann |
| |
Affiliation: | a Technische Universität Darmstadt, Department of Computer Science, Hochschulstraße 10, 64289 Darmstadt, Germany b Martin-Luther-Universität Halle-Wittenberg, Department of Computer Science, Von-Seckendorff-Platz 1, 06120 Halle (Saale), Germany |
| |
Abstract: | 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. |
| |
Keywords: | Shortest path Minor-closed graph classes Planar graph Steiner tree Mehlhorn&rsquo s algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|