Timeline for Find multiple non-adjacent paths in a graph
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 27, 2014 at 14:16 | answer | added | Daniel Soltész | timeline score: 2 | |
| Jun 27, 2014 at 11:40 | comment | added | Tony Huynh | This is certainly different from Menger's Theorem. For example in $K_n$, we can find $n-1$ internally disjoint paths from $s$ to $t$, but only two such paths (the edge $st$ and some other path) in the above sense. | |
| Jun 27, 2014 at 11:14 | comment | added | Daniel Soltész | If you put it this way, it is quite similar to Menger's theorem. But only one direction is immediate. We can bound from above the number of such paths by $min_{C} \alpha(C)$ where $C$ is a set of vertices that cuts $s$ from $t$. The other direction does not seem to be that easy, and it might happen that in your problem we can not achieve this upper bound. | |
| S Jun 27, 2014 at 11:05 | history | suggested | Ben Barber | CC BY-SA 3.0 |
tag and tidy
|
| Jun 27, 2014 at 10:58 | review | Suggested edits | |||
| S Jun 27, 2014 at 11:05 | |||||
| Jun 27, 2014 at 9:47 | answer | added | Delio Mugnolo | timeline score: 0 | |
| Jun 27, 2014 at 8:37 | history | asked | lchen | CC BY-SA 3.0 |