Timeline for Reconstructing a graph from shortest paths information
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 20, 2016 at 15:15 | comment | added | Mohammad Al-Turkistany | @monkeymaths Yes, another variant is restricting A to contain only distances greater than 2. | |
| Dec 20, 2016 at 14:44 | comment | added | monkeymaths | A more interesting question can be obtained if $A$ is not bound to contain distances between ALL pairs of vertices, but just between the vertices in some subset of $V(G)$. | |
| Dec 20, 2016 at 14:11 | vote | accept | Mohammad Al-Turkistany | ||
| Dec 20, 2016 at 13:57 | answer | added | Tony Huynh | timeline score: 3 | |
| Dec 20, 2016 at 13:50 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 194 characters in body
|
| Dec 20, 2016 at 13:41 | comment | added | Tony Huynh | Note that $uv$ is an edge of $G$ if and only if the distance between $u$ and $v$ is $1$. Thus, you know all the edges, and hence the entire graph (in polynomial-time). | |
| Dec 20, 2016 at 13:30 | history | asked | Mohammad Al-Turkistany | CC BY-SA 3.0 |