Timeline for Are there variants of Euclidean Steiner Tree problem that are known to be in P?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 13, 2023 at 18:19 | vote | accept | Nandakumar R | ||
| Jul 13, 2023 at 18:19 | |||||
| Jun 22, 2023 at 22:07 | comment | added | Gerry Myerson | Note that the references I found are from over 35 years ago. It's quite possible more is known by now. It might be worthwhile to try to find more recent papers that cite the ones I found. | |
| Jun 22, 2023 at 17:19 | comment | added | Nandakumar R | Thanks for the reference. As far as I could make out from it, although some results have proved (or conjecture) that under rather strong conditions, the steiner tree is the minimum spanning tree itself, not much is known about point distributions where one needs to actually use steiner points (iow, the steiner tree is not the spanning tree) and still achieve P complexity with some other algorithm. The full set of circumstances under which the min spanning tree gives the steiner tree also seems unknown. | |
| Jun 22, 2023 at 3:36 | history | answered | Gerry Myerson | CC BY-SA 4.0 |