Timeline for Is the partition of bipartite graphs NP-hard?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 30, 2018 at 9:34 | history | suggested | Rodrigo de Azevedo | CC BY-SA 4.0 |
Minor edits
|
| May 30, 2018 at 8:39 | comment | added | Brendan McKay | The maximum for non-empty sets occurs when $U_2$ and $V_2$ contain one vertex each. Just try all the possibilities. Note that the sum of the four $w(*,*)$ quantities is the total weight of all edges, so maximising your objective function is the same as minimising $w(U_1,V_2)+w(U_2,V_1)$. For any $U_1$, the first term achieves its minimum when $V_2$ is a singleton and similarly for the second term. | |
| May 30, 2018 at 8:10 | review | Suggested edits | |||
| S May 30, 2018 at 9:34 | |||||
| S May 30, 2018 at 7:18 | history | suggested | Rodrigo de Azevedo | CC BY-SA 4.0 |
Minor improvements
|
| May 30, 2018 at 5:55 | review | Suggested edits | |||
| S May 30, 2018 at 7:18 | |||||
| May 29, 2018 at 19:24 | comment | added | Thomas Edison | I assume it is nonempty | |
| May 29, 2018 at 19:21 | comment | added | Brendan McKay | The maximum is when $U_2=V_2=\emptyset$. | |
| May 29, 2018 at 14:50 | history | asked | Thomas Edison | CC BY-SA 4.0 |