Fast polynomial-space algorithms using inclusion-exclusion

Research output: Contribution to journalArticleAcademicpeer-review

38 Citations (Scopus)
2 Downloads (Pure)

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 languageEnglish
Pages (from-to)868-884
JournalAlgorithmica
Volume65
Issue number4
DOIs
Publication statusPublished - 2013
Externally publishedYes

Fingerprint Dive into the research topics of 'Fast polynomial-space algorithms using inclusion-exclusion'. Together they form a unique fingerprint.

  • Cite this