Minimum weight (T, d)-joins and multi-joins

AbstractA (T, d)-join arises as a natural generalization of the well-known notion of a T-join. Given a graph G = (V, E), a subset T of its nodes, and nonnegative integers ds for s ϵ T, a (T, d)-join is a set B ⊆ E which is representable as the union of pairwise edge-disjoint T-paths and circuits so that for each s ϵ T, exactly d, of these paths have one end at s. Here a T-path is a path connecting distinct elements of T.We give a description for the dominant of the set of (T, d)-joins. We also give a description for the dominant of the set of maximum multi-joins, where a multi-join is a subset of E representable as the union of pairwise edge-disjoint T-paths and circuits, and a multi-join is called maximum if the number of paths is as large as possible.Both results are derived from a minimax relation for the parametric minimum weight edge-disjoint T-paths problem, established in [9]