Timeline for Path cover with paths of bounded length, in the plane
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Dec 16, 2016 at 0:28 | answer | added | D.W.♦ | timeline score: 1 | |
| Dec 15, 2016 at 7:18 | history | tweeted | twitter.com/StackCompSci/status/809296483572969472 | ||
| Dec 14, 2016 at 16:13 | comment | added | j_random_hacker | Idea: If you have a pair of vertices $u, v$ such that $u$ is the nearest neighbour of $v$, then there is an optimal solution in which $u$ is not the endpoint of a path. (Suppose it was: Then delete any single edge adjacent to $v$ (there could be either 1 or 2 of these) and connect $v$ to $u$ instead for a solution with cost at least as good.) | |
| Dec 14, 2016 at 15:14 | comment | added | j_random_hacker | This is certainly NP-hard: given any Euclidean Longest Path problem, add a new vertex $r$ sufficiently far away from every vertex, and make $b$ big enough to allow all vertices to be contained in a single path. | |
| Dec 14, 2016 at 10:25 | history | edited | D.W.♦ | CC BY-SA 3.0 |
deleted 23 characters in body; edited tags
|
| Dec 14, 2016 at 10:18 | history | asked | D.W.♦ | CC BY-SA 3.0 |