Steiner Tree Dreyfus Wagner

Problem definition.

In the Steiner tree problem we are given the set of nonterminals, the set of terminals and the metric m. Our goal is to find a minimum cost tree connecting all terminals (it can possibly contain some nonterminal nodes).

Solution

This algorithm solves exact SteinerTree problem in exponential time in respect of number of terminals. Not an approximation algorithm by itself, it is used to solve subproblems in many other algorithms.

Example

#include "test/test_utils/sample_graph.hpp"

#include "paal/steiner_tree/dreyfus_wagner.hpp"

#include <boost/range/algorithm/copy.hpp>

#include <iostream>

int main() {
    // prepare metric
    typedef sample_graphs_metrics SGM;
    auto gm = SGM::get_graph_metric_steiner();

    // prepare terminals and Steiner vertices
    std::vector<int> terminals = { SGM::A, SGM::B, SGM::C, SGM::D };
    std::vector<int> nonterminals = { SGM::E };

    // run algorithm
    auto dw =
        paal::make_dreyfus_wagner(gm, terminals, nonterminals);
    dw.solve();

    // print result
    std::cout << "Cost = " << dw.get_cost() << std::endl;
    std::cout << "Steiner points:" << std::endl;
    boost::copy(dw.get_steiner_elements(),
              std::ostream_iterator<int>(std::cout, "\n"));
    std::cout << "Edges:" << std::endl;
    for (auto edge : dw.get_edges()) {
        std::cout << "(" << edge.first << "," << edge.second << ")"
                  << std::endl;
    }

    return 0;
}

example file is dreyfus_wagner_example.cpp

Complexity

Complexity of the algorithm is \(O(3^{|T|} * |V| + 2^{|T|} * |V|^2)\), where T is the set of terminals.

References

The algorithm is described in the [7].

See Also

• Steiner Tree 1.39 Approximation
• Steiner Tree 11/6 Approximation
• Steiner Tree Greedy