Timeline for Spanning tree minimizing $F_T = \sum_{i = 1}^{|V| - 1|} (w(e_i) - P_T)^2$
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 17, 2017 at 12:37 | history | undeleted | Todd Trimble | ||
| Oct 16, 2017 at 17:49 | history | deleted | Todd Trimble | via Vote | |
| Oct 16, 2017 at 17:49 | comment | added | Todd Trimble | Apologies for the possible inconvenience, but this question will have to be deleted, pending investigation of its allegedly being a competition problem. @befair Please write [email protected] with details. | |
| Oct 16, 2017 at 17:04 | comment | added | Gerhard Paseman | @befair You should alert the moderators with details of the competition. They can delete the question and then undelete it later. Gerhard "Spoilers Aren't Just For Movies" Paseman, 2017.10.16. | |
| Oct 16, 2017 at 16:53 | history | edited | J. Abraham | CC BY-SA 3.0 |
deleted 193 characters in body
|
| Oct 16, 2017 at 15:25 | comment | added | be fair | Please do not answer this question until midnight. There is a competition now and this task is one of the problems. | |
| Oct 16, 2017 at 13:19 | vote | accept | J. Abraham | ||
| Oct 16, 2017 at 7:20 | history | edited | Peter Heinig | CC BY-SA 3.0 |
Typos corrected.
|
| Oct 16, 2017 at 6:11 | history | edited | J. Abraham | CC BY-SA 3.0 |
added 197 characters in body
|
| Oct 15, 2017 at 20:10 | comment | added | Mikhail Tikhomirov | @J.Abraham Depending on the range of $k$, this may allow to make considerable optimizations. For instance, there is a simple $O(k|V| \alpha(|V|))$ algorithm along the same lines with my answer that uses the fact that there are only $O(k)$ different orders now, and that we can leave only $O(|V|)$ edges of each weight value (here $\alpha(|V|)$ is the inverse Ackermann function used in the disjoint set union data structure necessary for Kruskal's algorithm). | |
| Oct 15, 2017 at 19:58 | comment | added | J. Abraham | I am thinking... if the weights of the edges were constrained by some number $k$ would it change anything? Like, can we include this into complexity if weights of edges of $G$ are from $\{1, 2, ..., k\}$? | |
| Oct 15, 2017 at 19:53 | comment | added | Mikhail Tikhomirov | @PeterHeinig The result you are mentioning seems obsolete compared to the $O(|E|^2 \log V)$ solution in my answer. | |
| Oct 15, 2017 at 19:00 | comment | added | Peter Heinig | Re "UPD" : according to p. 9 in Naoki Katoh: An ϵ-approximation Scheme for Minimum Variance Combinatorial Problems. International Institute for Applied Systems Analysis Austria. WP-97-117, 1987, the minimum-variance spanning tree [ed.: this is the key technical term] can be solved in time $O(h(V,E)\cdot\lvert V\rvert\cdot\lvert E\rvert)$, where $h(V,E)$ denotes the # of steps required for finding an MST in $G=(V,E)$; and it's known that $h(V,E)\in O(\lvert E\rvert\cdot\min\{ i\in\omega\mid\ i>0,\log^{\circ i}(n)\leq\lvert E\rvert/\lvert V\rvert\})$. | |
| Oct 15, 2017 at 16:57 | history | edited | J. Abraham | CC BY-SA 3.0 |
added 12 characters in body
|
| Oct 15, 2017 at 15:26 | history | edited | J. Abraham | CC BY-SA 3.0 |
added 49 characters in body
|
| Oct 15, 2017 at 13:03 | answer | added | Peter Heinig | timeline score: 1 | |
| Oct 15, 2017 at 10:18 | history | edited | J. Abraham | CC BY-SA 3.0 |
edited body
|
| Oct 15, 2017 at 8:22 | answer | added | Mikhail Tikhomirov | timeline score: 5 | |
| S Oct 15, 2017 at 6:52 | history | edited | J. Abraham | CC BY-SA 3.0 |
English, Grammar and latex
|
| S Oct 15, 2017 at 6:52 | history | suggested | Amir Sagiv | CC BY-SA 3.0 |
English, Grammar and latex
|
| Oct 15, 2017 at 6:48 | review | Suggested edits | |||
| S Oct 15, 2017 at 6:52 | |||||
| Oct 15, 2017 at 6:29 | history | edited | Martin Sleziak | CC BY-SA 3.0 |
MathJax: \langle, \rangle
|
| Oct 15, 2017 at 6:24 | review | First posts | |||
| Oct 15, 2017 at 6:48 | |||||
| Oct 15, 2017 at 6:22 | history | asked | J. Abraham | CC BY-SA 3.0 |