Timeline for Complexity of a very simple graph partitioning problem
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 24, 2015 at 19:52 | vote | accept | Tom Solberg | ||
| Sep 10, 2015 at 2:07 | answer | added | Flo Pfender | timeline score: 2 | |
| Sep 9, 2015 at 17:35 | history | edited | Tom Solberg | CC BY-SA 3.0 |
Gerhard Paseman's suggestion
|
| Sep 9, 2015 at 17:34 | comment | added | Tom Solberg | @GerhardPaseman, sure, the problem as stated is a feasibility problem, but one could certainly search for the minimal $r$ that ensures connectivity. | |
| Sep 9, 2015 at 17:27 | comment | added | Gerhard Paseman | In particular, if G has a vertex v with distance greater than r to all other vertices, then v can't belong to any of the k subsets. Are you promising anything with respect to r, or is an additional goal to find a minimal such r? Gerhard "The Problem Behind The Problem?" Paseman, 2015.09.09 | |
| Sep 9, 2015 at 17:23 | comment | added | Gerhard Paseman | You are going to need r big enough so that such a decomposition is remotely possible. I'm thinking that the subgraph T_r of G which contains only edges of length less than r has to be k-connected or something along those lines. Are there quick ways to determine if T_r "might be connected enough"? Gerhard "Maybe A Simpler Hard Problem" Paseman, 2015.09.09 | |
| Sep 9, 2015 at 17:09 | history | asked | Tom Solberg | CC BY-SA 3.0 |