  We study multi-marginal optimal transport (MOT) problems where the underlying
cost has a graphical structure. These graphical multi-marginal optimal
transport problems have found applications in several domains including traffic
flow control and regression problems in the Wasserstein space. MOT problem can
be approached through two aspects: a single big MOT problem, or coupled minor
OT problems. In this paper, we focus on the latter approach and demonstrate it
has efficiency gain from the parallelization. For tree-structured MOT problems,
we introduce a novel parallelizable algorithm that significantly reduces
computational complexity. Additionally, we adapt this algorithm for general
graphs, employing the modified junction trees to enable parallel updates. Our
contributions, validated through numerical experiments, offer new avenues for
MOT applications and establish benchmarks in computational efficiency.
