Variation in which the objective is to minimize the number of rounds
that together connect all pairs, is approximable within
on general multigraphs and
within
on butterfly graphs
[447].
MINIMUM PATH COLORING is the variation in which each path is assigned
a color, where only paths with the same color need to be edge disjoint, and
where the objective is to minimize the number of colors that are needed to
connect all vertex pairs in the input. This problem
is approximable within 3/2 on trees, within 2 on cycles [415],
within
on two-dimensional meshes
[412], and within
on nearly-Eulerian uniformly
high-diameter planar graphs [324].