Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions

DOI10.1007/s00453-014-9934-0zbMath1312.68230arXiv1305.7448MaRDI QIDQ2343089

Hans L. Bodlaender, Jesper Nederlof, Stefan Fafianie

Publication date: 4 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.7448

zbMATH Keywords

dynamic programming; treewidth; Steiner tree; exact algorithms; algorithm engineering; experimental evaluation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

90C39: Dynamic programming

05C85: Graph algorithms (graph-theoretic aspects)

Uses Software

• SteinLib
• GeoSteiner
• Treewidthlib
• ComputeTW