Timeline for Finding a vertex equidistant from two given vertices in a digraph
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 5, 2013 at 13:50 | vote | accept | Vidit Nanda | ||
| Feb 5, 2013 at 10:52 | answer | added | Andrej Bauer | timeline score: 5 | |
| Feb 5, 2013 at 10:19 | answer | added | Brendan McKay | timeline score: 2 | |
| Feb 5, 2013 at 5:27 | comment | added | Gerhard Paseman | Aaron's suggestion makes me think that there is a reduction from the Frobenius coin problem to this one. However, the reduction I am thinking of is exponential; it may be that doing a reduction in the other direction will yield a polynomial time solution (to borrow Aaron's example, polynomial in 6, 10 and 15 and not polynomial in their logs). I don't see such a reduction being more clever than Aaron's adjacency matrix suggestion. Gerhard "Reduce, Recycle, And Reuse Mathematics" Paseman, 2013.02.04 | |
| Feb 5, 2013 at 3:58 | comment | added | Aaron Meyerowitz | What are the graphs like ? If there are directed cycles A,B,C of lengths 6,10,15 (or any list of cycles whose combined lengths have gcd 1) which can be visited in that order from both x and y then yes. If $A$ is the adjacency matrix then you could compute $A^2$,$A^4$ etc. If there is a z with non zero value in both the xz and yz positions in any one of these (for example if one has all entries positive then again yes. Is that path counting? | |
| Feb 5, 2013 at 1:53 | comment | added | Vidit Nanda | Joseph, the paths don't need to be simple unfortunately. | |
| Feb 5, 2013 at 1:50 | comment | added | Joseph O'Rourke | Must the paths be simple? Suppose $\gamma$ includes a cycle of length $k$. Then one could repeat the cycle and lengthen the path by $k, 2k, 3k, \ldots$ while still reaching the same vertices. | |
| Feb 5, 2013 at 1:39 | history | asked | Vidit Nanda | CC BY-SA 3.0 |