Premium
Length‐constrained path‐matchings in graphs
Author(s) -
Ghodsi M.,
Hajiaghayi M. T.,
Mahdian M.,
Mirrokni V. S.
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10030
Subject(s) - vertex (graph theory) , computer science , disjoint sets , matching (statistics) , combinatorics , path (computing) , time complexity , vertex cover , multicast , set (abstract data type) , graph , mathematics , theoretical computer science , computer network , statistics , programming language
Abstract 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. © 2002 Wiley Periodicals, Inc.