Skip to main content
MathOverflow

Return to Question

grammar corrections
Source Link
edit approved Oct 17, 2018 at 11:32
Glorfindel
edit approved Oct 17, 2018 at 11:32
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

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

AreDo 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))$?

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

Are there exist advanced results on 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))$?

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))$?

Source Link
gsv
gsv
  • 111
  • 2

Single source shortest path over non-commutative finite idempotent semiring in Cartesian product

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

Are there exist advanced results on 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))$?