Timeline for Need a graph theory problem with nontrivial faster approximation algorithm
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 2, 2016 at 11:58 | answer | added | Mark Bell | timeline score: 1 | |
| Sep 2, 2016 at 11:10 | answer | added | Vinicius dos Santos | timeline score: 1 | |
| Aug 5, 2016 at 4:10 | history | edited | jsliyuan | CC BY-SA 3.0 |
added 197 characters in body
|
| Aug 4, 2016 at 7:01 | comment | added | jsliyuan | Yes, MST is in P. There is O(|E|log|V|) algorithm solving MST. The definition of c-approximation makes sense for any optimization problem. I mean, is there is a linear-time, that is, O(|E|), algorithm which gives constant-factor approximation algorithm for MST? | |
| Aug 4, 2016 at 6:54 | comment | added | mhsnk | Minimum Spanning Tree is not an NP-Hard problem and Polynomial time algorithms like Prim and Kruskal exist for MST. What do you mean by approximation algorithm for a problem which is not NP-Hard? | |
| Aug 4, 2016 at 6:26 | history | asked | jsliyuan | CC BY-SA 3.0 |