Timeline for Partition of a graph into subgraphs with small maximum degree
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2021 at 8:17 | comment | added | Tony Huynh | For $k=2$, a global minimum cut has the desired property and can be found via Karger's algorithm. en.wikipedia.org/wiki/Karger%27s_algorithm | |
| Oct 14, 2021 at 6:17 | comment | added | TheEmeritus | Thanks. But attempting to write an algorithm to find such a partition seems pretty hard, looking at the above description? | |
| Aug 17, 2016 at 19:15 | history | edited | Tony Huynh | CC BY-SA 3.0 |
edited body
|
| Aug 17, 2016 at 18:43 | history | answered | Tony Huynh | CC BY-SA 3.0 |