3
$\begingroup$

I am using the algorithm implemented by the library networkx to solve a Steiner minimal tree problem.

They claim their algorithm to give an approximated solution.

However, I am working on a specific group of graphs, namely, grid lattices (with capacity 1).

I believe this group of circuit belongs the Euclidean group, which should be hard to solve as well(?).

On my experiments I keep getting the optimal solutions, so I wonder what property my graph has to guarantee that. Is it because of the capacity? Or maybe because it is a grid?

$\endgroup$

1 Answer 1

1
$\begingroup$

The problem is NP-hard in general. I suspect that your problems are rather small or have few terminals and are therefore easy to solve, even for an approximation algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.