Timeline for Compute number vertex disjoint cycles in graph surrounding a face
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 3, 2010 at 14:52 | comment | added | momeara | Sorry for the confusion--I've added some clarifications that hopefully address some of your concerns. Thanks. | |
| Oct 3, 2010 at 12:25 | comment | added | Tony Huynh | Hi momeara. I'll just remark that embedded in $\mathbb{R}^2$ often means planar, although it could mean drawn with edge crossings too. I'll stick with your terminology from now on. Even so, your example is a bit confusing, because it looks like we can only pack one cycle containing $t$. | |
| Oct 3, 2010 at 5:30 | comment | added | momeara | Hi Tony, $G$ need not be planar. Here is an example where I believe a greedy approach fails. garin.med.unc.edu/~momeara/… | |
| Oct 2, 2010 at 23:42 | history | edited | Tony Huynh | CC BY-SA 2.5 |
added 14 characters in body
|
| Oct 2, 2010 at 23:30 | comment | added | Tony Huynh | Yes, $t$ is the closest cycle to itself and may be included in any maximum collection of disjoint cycles containing $t$. Once we agree that $t$ is in said collection, then we may as well include the 'next closest' cycle to $t$. This is the cycle that I'm talking about | |
| Oct 2, 2010 at 23:06 | comment | added | Andrew D. King | I don't understand why you don't just say that the closest cycle to $t$ is $t$ itself. Or are you now dropping the assumption that the graph is 2-connected? | |
| Oct 2, 2010 at 21:32 | history | answered | Tony Huynh | CC BY-SA 2.5 |
