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

DOI10.1007/978-3-319-03898-8_27MaRDI QIDQ2867093zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Stefan Fafianie, Jesper Nederlof, Hans L. Bodlaender

Publication date 10 December 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-03898-8_27

zbMATH Keywords

dynamic programmingtreewidthexact algorithmsSteiner treeexperimental evaluationalgorithmic engineering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Nonnumerical algorithms (68W05)

Recommendations

• Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Cut and count and representative sets on branch decompositions
• Dynamic programming for minimum Steiner trees
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Improving the efficiency of dynamic programming on tree decompositions via machine learning

Cited in

(5)

• Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm
• New analysis and computational study for the planar connected dominating set problem
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Strong Steiner tree approximations in practice

Describes a project that uses

Uses Software

• Treewidthlib
• GeoSteiner
• SteinLib

This page was built for publication: Speeding up dynamic programming with representative sets. An experimental evaluation of algorithms for Steiner Tree on tree decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867093)