Separator-Based Pruned Dynamic Programming for Steiner Tree
Abstract
Steiner tree is a classical NP-hard problem that has been extensively studied both theoretically and empirically. In theory, the fastest approach for inputs with a small number of terminals uses the dynamic programming, but in practice, stateof-the-art solvers are based on the branch-and-cut method. In this paper, we present a novel separator-based pruning technique for speeding up a theoretically fast DP algorithm. Our empirical evaluation shows that our pruned DP algorithm is quite effective against real-world instances admitting small separators, scales to more than a hundred terminals, and is competitive with a branch-and-cut solver.
Cite
Text
Iwata and Shigemura. "Separator-Based Pruned Dynamic Programming for Steiner Tree." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33011520Markdown
[Iwata and Shigemura. "Separator-Based Pruned Dynamic Programming for Steiner Tree." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/iwata2019aaai-separator/) doi:10.1609/AAAI.V33I01.33011520BibTeX
@inproceedings{iwata2019aaai-separator,
title = {{Separator-Based Pruned Dynamic Programming for Steiner Tree}},
author = {Iwata, Yoichi and Shigemura, Takuto},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {1520-1527},
doi = {10.1609/AAAI.V33I01.33011520},
url = {https://mlanthology.org/aaai/2019/iwata2019aaai-separator/}
}