Fulltext

Computing Optimal Steiner Trees in Polynomial Space

Fomin, Fedor ; Grandoni, Fabrizio ; Kratsch, Dieter ; Lokshtanov, Daniel ; Saurabh, Saket

In: Algorithmica, 2013, vol. 65, no. 3, p. 584-604

Aggiungi alla tua lista
    Titre
    • Computing Optimal Steiner Trees in Polynomial Space
    Auteur
    • Fomin, Fedor. Department of Informatics, University of Bergen, 5020, Bergen, Norway
    • Grandoni, Fabrizio. IDSIA, University of Italian Switzerland, Galleria 1, 6928, Manno, Switzerland
    • Kratsch, Dieter. LITA, Université Paul Verlaine - Metz, 57045, Metz Cedex 01, France
    • Lokshtanov, Daniel. Department of Informatics, University of Bergen, 5020, Bergen, Norway
    • Saurabh, Saket. The Institute of Mathematical Sciences, Taramani, 600 113, Chennai, India
    Type de document
    • Postprint
    Identifiant OAI-PMH
    • oai:doc.rero.ch:315044
    Summary
    Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 n )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) k n O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to $O(4^{k}n^{O(\log^{2} k)})$ . This improves on trivial enumeration for roughly k