Key points are not available for this paper at this time.
Given an edge-colored graph Gc, a set of p pairs of vertices (aᵢ, bᵢ) together with p numbers k₁, k₂, kₚ associated with the pairs, can we find a set of alternating paths linking the pairs (a₁, b₁), (a₂, b₂), , in their respective numbers k₁, k₂, kₚ? Such is the question addressed in this paper. The problem being highly intractable, we consider a restricted version of it to edge-colored complete graphs. Even so restricted, the problem remains intractable if the paths/trails must be edge-disjoint, but it ceases to be so if the paths/trails are to be vertex-disjoint, as is proved in this paper. An approximation algorithm is presented in the end, with a performance ratio asymptotically close to 3/4 for a restricted version of the problem.
Rachid Saad (Sat,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: