Two disjoint shortest paths in the equal-hop path construction

At least 12 years old · documented by

Let kk be a node that is neither the source nor a virtual source. Let i0i_{0}, i1i_{1}, j0j_{0}, and j1j_{1} be the quantities defined in Equations and. Let c0c_{0} and c1c_{1} be the two colors different from the color of kk, and suppose that

i1−i0=j1−j0.i_{1}-i_{0}=j_{1}-j_{0}.

Two-path conjecture. Node kk always has two disjoint shortest paths p0p_{0} and p1p_{1} satisfying one of the following alternatives: (1) p0p_{0} runs from X0X_{0} through the color-c0c_{0} neighbors to kk, while p1p_{1} runs from X1X_{1} through the color-c1c_{1} neighbors to kk; or (2) p0p_{0} runs from X0X_{0} through the color-c1c_{1} neighbors to kk, while p1p_{1} runs from X1X_{1} through the color-c0c_{0} neighbors to kk. Here, an hh-hop path set is a set of paths all having length hh, so the assertion concerns shortest paths in the colored network construction. The claim is a structural property used to establish the relationship between the network equations and the existence of suitable disjoint paths; its resolution is not specified in the supplied text.

References

Primary source

Shen Feng and Soung C. Liew, “Wireless Broadcast with Physical-Layer Network Coding”, arXiv:1303.7054 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.