direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Speeding Up Dynamic Programming with Representative Sets - An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions

Stefan Fafianie (Universiteit Utrecht, The Netherlands)

In a recent experimental evaluation we have compared the classic
dynamic algorithm for Steiner Tree on tree decompositions with an
improved algorithm by Bodlaender et al. in which the size of tables
calculated during the algorithm is reduced intermittently using the
notion of representative sets. In this talk we will recall the
algorithm and the key idea for the table reductions. We will then show
the experimental results on a variety of instances.

Date
Speaker
Location
Language
02.10.2013 16:15
Stefan Fafianie
TEL 512
english

Back to the research colloquium site.

Zusatzinformationen / Extras