English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Steiner tree problem is a well-known problem in network design, routing,and VLSI design. Given a graph, edge costs, and a set of dedicated vertices(terminals), the Steiner tree problem asks to output a sub-graph that connectsall terminals at minimum cost. A state-of-the-art algorithm to solve theSteiner tree problem by means of dynamic programming is the Dijkstra-Steineralgorithm. The algorithm builds a Steiner tree of the entire instance bysystematically searching for smaller instances, based on subsets of theterminals, and combining Steiner trees for these smaller instances. The searchheavily relies on a guiding heuristic function in order to prune the searchspace. However, to ensure correctness, this algorithm allows only for limitedheuristic functions, namely, those that satisfy a so-called consistencycondition. In this paper, we enhance the Dijkstra-Steiner algorithm andestablish a revisited algorithm, called DS*. The DS* algorithm allows forarbitrary lower bounds as heuristics relaxing the previous condition on theheuristic function. Notably, we can now use linear programming based lowerbounds. Further, we capture new requirements for a heuristic function in acondition, which we call admissibility. We show that admissibility is indeedweaker than consistency and establish correctness of the DS* algorithm whenusing an admissible heuristic function. We implement DS* and combine it withmodern preprocessing, resulting in an open-source solver (DS* Solve). Finally,we compare its performance on standard benchmarks and observe a competitivebehavior.

Solving the Steiner Tree Problem with few Terminals