Length-constrained path-matchings in graphs
The path-matching problem is to find a set of vertex- or edge-disjoint paths with length constraints in a given graph with a given set of endpoints. This problem has several applications in broadcasting and multicasting in computer networks. In this paper, we study the algorithmic complexity of different cases of this problem. In each case, we either provide a polynomial-time algorithm or prove that the problem is NP-complete. (C) 2002 Wiley Periodicals, Inc.
path-matching algorithms np-completeness matching pseudo-matching