Timeline for Efficient computation of a vertex-partition for graphs
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 1, 2011 at 4:54 | answer | added | Aaron Meyerowitz | timeline score: 1 | |
| Oct 11, 2010 at 14:16 | comment | added | Roland Bacher | Nice reformulation! | |
| Oct 11, 2010 at 13:58 | comment | added | Dave Pritchard | Maybe it is easier to reformulate in the following way: two vertices $u, v$ are in the same partition iff $\sum_T d_T(u, v)$ is even, where the inner expression is the distance in the tree. Is there a nice way to compute this distance sum mod 2? | |
| Sep 13, 2010 at 21:57 | comment | added | JBL | Apurva, there's a product over all spanning trees. | |
| Sep 13, 2010 at 21:36 | comment | added | Apurva | Is the spanning tree $T$ a given at the beginning of this problem, or is it a part of the problem to also find the spanning tree? | |
| Sep 13, 2010 at 16:05 | comment | added | Roland Bacher | Thank you. That's a typical error of french-speaking people, I guess. | |
| Sep 13, 2010 at 14:19 | comment | added | JBL | @Roland, in English "to ignore" means "to refuse to notice; to disregard" -- to convey "to not know" one can write "to be ignorant of." | |
| Sep 13, 2010 at 13:48 | comment | added | Roland Bacher | Concerning the name of this bipartition, I ignore the answer. Concernings Austin Mohr's remark: Of course, the function is only used for defining an equivalence relation with at most two classes on the set of vertices. | |
| Sep 13, 2010 at 13:06 | comment | added | Austin Mohr | Just a minor point: Your function appears to be defined on $V(\Gamma) \times V(\Gamma)$, as $\phi_T$ only has a meaningful output when given two vertices. | |
| Sep 13, 2010 at 11:50 | comment | added | Nathann Cohen | Does this partition have a name ? :-) | |
| Sep 13, 2010 at 11:19 | answer | added | sleepless in beantown | timeline score: 0 | |
| Sep 13, 2010 at 8:07 | history | asked | Roland Bacher | CC BY-SA 2.5 |