Fast polynomial-space algorithms using inclusion-exclusion

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

42 Citaten (Scopus)
2 Downloads (Pure)


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
Originele taal-2Engels
Pagina's (van-tot)868-884
Nummer van het tijdschrift4
StatusGepubliceerd - 2013
Extern gepubliceerdJa

Vingerafdruk Duik in de onderzoeksthema's van 'Fast polynomial-space algorithms using inclusion-exclusion'. Samen vormen ze een unieke vingerafdruk.

Citeer dit