Let $G$ be a Cartesian product of two arbitrary directed weighted graphs $M$ and $N$. The weights are from a non-commutative finite idempotent semiring.

Do there exist advanced results on the single source shortest path (SSSP) problem for $G$? Suppose that $|V_M| = |V_N| = n$. Is it possible to solve SSSP in $\widetilde{O}(BMM(n))$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.