Timeline for Even sign configurations with prescribed support
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Dec 19, 2012 at 9:40 | comment | added | Roland Bacher | @domotorp: I got effectively a little bit confused about complexity-issues for perfect matchings: part of the confusion arose out of the similar notions of maximal matching (a matching which cannot be extended to a larger matching) and maximum matching (involving the largest possible number of edges). I first believed that only finding a maximal matching is in P (which is of course easy). | |
| Dec 18, 2012 at 19:01 | comment | added | Tony Huynh | @domotorp: I think it was an honest mistake by Roland, since he must have assumed that you meant that finding a perfect matching is only in P for graphs of maximum degree 4. Indeed, the main point of my answer was just to clear up this confusion. | |
| Dec 18, 2012 at 18:49 | comment | added | domotorp | Why would you write that after my comment it seems that finding a matching is NP-complete when I wrote that it is in P? Whatever... | |
| Dec 18, 2012 at 17:20 | history | edited | Roland Bacher | CC BY-SA 3.0 |
added 51 characters in body; Post Made Community Wiki
|
| Dec 18, 2012 at 17:16 | vote | accept | Roland Bacher | ||
| Dec 18, 2012 at 16:59 | answer | added | Tony Huynh | timeline score: 2 | |
| Dec 18, 2012 at 16:52 | history | edited | Roland Bacher | CC BY-SA 3.0 |
added 247 characters in body
|
| Dec 18, 2012 at 16:37 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
improve markup
|
| Dec 18, 2012 at 15:44 | history | edited | Roland Bacher | CC BY-SA 3.0 |
added 304 characters in body
|
| Dec 18, 2012 at 15:36 | history | edited | Roland Bacher | CC BY-SA 3.0 |
added 435 characters in body
|
| Dec 18, 2012 at 15:29 | comment | added | Roland Bacher | @domotorp: Your first comment refers to a bugged version containing the wrong definition, I have corrected it since. I do not know if this answers your second question. But if finding a matching in an arbitrary graph is in P the answer to my question is YES (you cannot suppose that the degree is $4$ however). | |
| Dec 18, 2012 at 15:24 | history | edited | Roland Bacher | CC BY-SA 3.0 |
added 25 characters in body
|
| Dec 18, 2012 at 15:22 | comment | added | domotorp | I also don't see why this question is similar to the grid-matching problem, but if you remove the intersection condition there, then it is just about finding a matching in a graph (with max degree 4), so it is in P. | |
| Dec 18, 2012 at 15:17 | history | edited | Roland Bacher | CC BY-SA 3.0 |
added 157 characters in body; deleted 11 characters in body; added 1 characters in body
|
| Dec 18, 2012 at 15:16 | comment | added | domotorp | I don't get it - if A has a row or column with an odd number of 1's, it cannot have an even sign configuration, while if this is not the case, you can pick M=A. | |
| Dec 18, 2012 at 15:09 | history | edited | Roland Bacher | CC BY-SA 3.0 |
added 18 characters in body
|
| Dec 18, 2012 at 15:04 | history | edited | Roland Bacher | CC BY-SA 3.0 |
added 43 characters in body
|
| Dec 18, 2012 at 14:30 | history | asked | Roland Bacher | CC BY-SA 3.0 |