Abstract
Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in O¿(2kc) time and O¿(c) space, where the O¿ notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give O¿(2n)-time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.
Keywords: Inclusion-Exclusion; Fixed parameter tractability; Exact algorithms; Polynomial space; Steiner tree
Original language | English |
---|---|
Pages (from-to) | 868-884 |
Journal | Algorithmica |
Volume | 65 |
Issue number | 4 |
DOIs | |
Publication status | Published - 2013 |
Externally published | Yes |