Open annieqt opened 8 years ago
Hi
First of all, thank you for being interested in my work. I'm always glad to be useful to someone.
However, I'm not sure to understand your first question.
A (directed) Steiner subgraph is a subgraph linking the root to every terminal. Thus, if I return the union of all the shortest paths from the root to the terminals, I return a Steiner subgraph. 2 remarks. 1) Of course, it is not (always) an optimal steiner tree, or we would prove the Steiner problem to be polynomial, and it is not unless P = NP. 2) The answer is always a tree because the Dijkstra algorithm returns a shortest paths tree from the root to every nodes and the answer SHP returns is a subgraph of that tree.
For your second question, I'm not sure there is any paper describing this algorithm because, as you say, it is a quite natural way to find a steiner tree, and the approximation ratio is an "easy to find" result. So I do not think a paper containing only this result would be accepted. Moreover, if I'm not wrong, in a paper from Charikar et al., "Approximation algorithms for Directed Steiner problems", there is a paragraph about it.
BR
Hi BR, Thanks for your kindly reply! I read the paper you mentioned and it is useful for me. I was searching for code that can construct a Steiner tree in an undirected graph but didn't even find a single piece of clean code for that, lol. Maybe I'll just use that easy way instead. Thanks!
Hi
Well, you have two solutions :
Mouton5000 (br was for best regards :) )
Hi bro, I was searching implementation of algorithms of constructing Steiner Trees and just came across your repository "DSTAlgoEvaluation". It really helped me a lot. I noticed that you've implemented four algorithms and I'm curious about the last one. I read your comment: "computes all the shortest path from the root using the Dijkstra algorithm and compute the union of all the shortest path from the root to the terminals". It's quite aN intuitive way of finding a Steiner Tree, but I wonder how would you prove this to be correct? Did you come up with this by yourself accidentally or do you read some papers about it? Thanks!