Paper Info

Title | ||
---|---|---|

Improved steiner tree algorithms for bounded treewidth |

Abstract | ||
---|---|---|

We propose a new algorithm that solves the Steiner tree problem on graphs with vertex set V to optimality in $\ensuremath{\mathcal{O}(B_{\ensuremath{\textit{tw}}+2}^2 \cdot \ensuremath{\textit{tw}}\ \cdot |V|)}$ time, where $\ensuremath{\textit{tw}}$ is the graph's treewidth and the Bell numberBk is the number of partitions of a k-element set. This is a linear time algorithm for graphs with fixed treewidth and a polynomial algorithm for $\ensuremath{\textit{tw}} = \ensuremath{\mathcal{O}(\log|V|/\log\log|V|)}$. While being faster than the previously known algorithms, our thereby used coloring scheme can be extended to give new, improved algorithms for the prize-collecting Steiner tree as well as the k-cardinality tree problems. |

Year | DOI | Venue |
---|---|---|

2012 | 10.1016/j.jda.2012.04.016 | Journal of Discrete Algorithms |

Keywords | DocType | Volume |

linear-time algorithm,new algorithm,improved steiner tree algorithm,polynomial algorithm,bounded treewidth,steiner tree problem,linear time algorithm,prize-collecting steiner tree,k-element set,improved algorithm,k-cardinality tree problem,bell numberbk,bell numberb,fixed treewidth | Journal | 16, |

ISSN | Citations | PageRank |

1570-8667 | 11 | 0.66 |

References | Authors | |

21 | 3 |

Authors (3 rows)

Cited by (11 rows)

References (21 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Markus Chimani | 1 | 301 | 35.55 |

Petra Mutzel | 2 | 596 | 42.63 |

Bernd Zey | 3 | 30 | 4.42 |