Timeline for Reference Request: designing a tree of "main roads" in a graph
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 26, 2018 at 11:16 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Feb 24, 2018 at 11:09 | comment | added | Peter Heinig | Dear @Lwins: the only aspect which actually changed mathematically is that I now have made $D$ a sum over $V\setminus U$ instead of $V$, because the latter was simply false: in order to model you prescription that the use of roads in $T$ be cost-free, one must not add distances between vertices inside $U$ to the sum $D$, because these distances in all nontrivial situations are larger than one, hence do add to the cost. In the unlikely case that I misundertood your intentions, please re-edit. | |
| Feb 24, 2018 at 11:06 | comment | added | Peter Heinig | Dear @Lwins: I made heavy edits to this post, all of which I think improve the post. E.g. I changed '$n$' to '$s$', because it is confusing to use $n$ for something other than the order. I think I did not change a single contentual aspect. In particular, while tempted to change that, I retained the curious condition that the number of vertices of the tree be strictly smaller than the number of the ambient graph. This is odd because you thus rule out that your 'main road tree' is a spannig tree, which is means that not every localtion will be accessible via a main road. Did you intend this? | |
| Feb 24, 2018 at 11:06 | history | edited | Peter Heinig | CC BY-SA 3.0 |
While this was bumped to the top anyway, I did a complete rewrite of the question. The content was preserved, down to the unmotivated detail that the OP requires that the 'main road tree' be *not* a spanning tree. I corrected a downright false detail: the sum was over $V$, not $V\setminus U$.
|
| Feb 24, 2018 at 10:30 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jan 25, 2018 at 9:44 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 26, 2017 at 9:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 26, 2017 at 8:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 27, 2017 at 7:08 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 4, 2017 at 5:24 | comment | added | Manfred Weis | Setting the weights tree edges to 0 can't be distinguished from setting all edges of the subgraph induced by the tree vertices on basis of the optimality of the solution. The problem has an LP solution, but is in NP because it contains the connectivity constraints of the induced subgraph; see for example the link mathoverflow.net/a/282317/31310 in the answert to my question mathoverflow.net/questions/282302/… | |
| Sep 27, 2017 at 10:41 | comment | added | Lwins | @ManfredWeis All edges have no weight, or equivalently, weight $1$. | |
| Sep 27, 2017 at 10:39 | comment | added | Manfred Weis | what are the weights of the edges in your counter example, Euclidean distances or $1$? would be interesting to calculate the solution my algorithm reports, when using specific edgeweights and if shortest paths are unique. | |
| Sep 27, 2017 at 6:30 | history | edited | Lwins | CC BY-SA 3.0 |
added 173 characters in body
|
| Sep 27, 2017 at 5:43 | answer | added | Manfred Weis | timeline score: 1 | |
| Sep 27, 2017 at 5:00 | comment | added | Lwins | @ManfredWeis Yes, it is exactly what I meant. | |
| Sep 27, 2017 at 4:58 | comment | added | Manfred Weis | So, could you please make more explicit, what is fixed and what has to be determined by the algorithm? Maybe you want to identify a tree of size $n < |V|$ in $G$, that minimizes the sum of pairwise distances of vertices in $G$ if its edge weights of $T$ are set to 0? | |
| Sep 27, 2017 at 3:56 | comment | added | Lwins | @ManfredWeis Unluckily the original paths does not need to be used after. | |
| Sep 27, 2017 at 3:53 | comment | added | Manfred Weis | Is the set $U$ fixed, but arbitrary and is it assumed that original paths are still used, after the cost of the tree edges has been set to 0? If that is the case, then an efficient algorithm exists | |
| S Sep 26, 2017 at 14:00 | history | suggested | monkeymaths | CC BY-SA 3.0 |
The term 'spanning tree' was misused, since such a tree contains all the vertices of the graph.
|
| Sep 26, 2017 at 13:45 | review | Suggested edits | |||
| S Sep 26, 2017 at 14:00 | |||||
| Sep 26, 2017 at 13:45 | comment | added | Joseph O'Rourke | There has been work on geometric versions in the plane (instead of a graph), and already this is complicated for placement of a single highway. E.g., Cardinal, J., Collette, S., Hurtado, F., Langerman, S., & Palop, B. (2008). Optimal location of transportation devices. Computational Geometry, 41(3), 219-229. PDF download | |
| Sep 26, 2017 at 13:00 | history | edited | Lwins | CC BY-SA 3.0 |
added 1 character in body; edited title
|
| Sep 26, 2017 at 12:51 | history | asked | Lwins | CC BY-SA 3.0 |