Timeline for Cubic graphs which are "difficult to navigate"
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 27, 2014 at 16:16 | vote | accept | Robin Saunders | ||
| Oct 20, 2011 at 23:15 | answer | added | Aubrey da Cunha | timeline score: 1 | |
| Jul 28, 2011 at 10:18 | comment | added | Robin Saunders | Uniformly distributed, otherwise "mean square shortest path length" doesn't make sense. | |
| Jul 28, 2011 at 5:01 | comment | added | user5810 | "mean square search time" for a uniformly distributed ordered pair of vertices, or for the worst-case ordered pair of vertices? | |
| Jul 28, 2011 at 4:27 | answer | added | Gerhard Paseman | timeline score: 1 | |
| Jul 28, 2011 at 4:01 | history | edited | Robin Saunders | CC BY-SA 3.0 |
corrected malapropism
|
| Jul 28, 2011 at 3:56 | comment | added | Robin Saunders | Yes, they are. I was kind of assuming you wouldn't turn around partway along an edge and go back to choose a different one, but I suppose technically there'd be nothing to stop you from doing that. | |
| Jul 28, 2011 at 1:57 | comment | added | user5810 | I just noticed: "distances to the adjacent vertices". Are these weighted graphs? | |
| Jul 28, 2011 at 1:40 | comment | added | Robin Saunders | @Ricky: I am restricting to simple graphs, and assuming that vertices can be recognized once they have been reached but edges can not be recognized from one end if they have only been seen from the opposite end. @Steve: I can see how that problem is related, but I am not sure to what extent. In particular, the graphs described in that paper have a very specific structure (in fact, they are technically not cubic), which seems to be key to the algorithms considered. | |
| Jul 28, 2011 at 1:00 | comment | added | Gerhard Paseman | Oops, I mean $9n$ for the linear version. For the branched version, it will again be an O(n) algorithm with the constant not too large, if you are allowed to remember what branches you finished. Gerhard "Ask Me About System Design" Paseman, 2011.07.27 | |
| Jul 28, 2011 at 0:57 | comment | added | Gerhard Paseman | This sounds like the cow-path problem. A linear version is as follows: a robot can traverse a number line back and forth to find an apple placed on it somewhere. What are upper and lower bounds on the number of (unit distance) steps needed to find the apple given the apple is $n$ units away (although the robot does not know $n$ or even if it is in the plus or minus direction). If I am right in guessing this is a similar problem, the answer is something like 9n. Gerhard "Walking And Searching For Similarities" Paseman, 2011.07.27 | |
| Jul 28, 2011 at 0:57 | comment | added | user5810 | Once you reach both of them, can you tell whether or not the $m$-th vertex you reached is the same as the $n$-th vertex you reached? Can you tell whether two edge parts you've seen are part of the same edge? Do you restrict to simple graphs? | |
| Jul 28, 2011 at 0:51 | comment | added | Steve Huntsman | arxiv.org/abs/quant-ph/0209131 | |
| Jul 28, 2011 at 0:11 | history | asked | Robin Saunders | CC BY-SA 3.0 |