Name
Abstract | ||
|---|---|---|
Given a simple and undirected graph, nonnegative node weights, a nonnegative integer j, and a positive integer k, a k-matching in the graph is a subgraph with no isolated nodes and with maximum degree no more than k, a j-restricted k-matching is a k-matching with each connected component having at least j + 1 edges, and the total node weight of a j-restricted k-matching is the total weight of the nodes covered by the edges in the j-restricted k-matching. When j = 1 and k = 2, Kaneko [Kaneko A (2003) A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two. J. Combin. Theory, B 88:195-218] and Kano et al. [Kano M, Katona G, Kiraly Z (2005) Packing paths of length at least two. Discrete Math. 283:129-135] studied the problem of maximizing the number of nodes covered by the edges in a 1-restricted 2-matching. In this paper, we consider the problem of finding a j-restricted k-matching with the maximum total node weight. We present a polynomial-time algorithm for the problem as well as a min-max theorem in the case of j < k. We also prove that, when j >= k >= 2, the problem of maximizing the number of nodes covered by the edges in a j-restricted k-matching is NP-hard. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1287/moor.2013.0624 | MATHEMATICS OF OPERATIONS RESEARCH |
Keywords | DocType | Volume |
k-matching,polynomial-time algorithm,min-max theorem,NP-completeness | Journal | 39 |
Issue | ISSN | Citations |
3 | 0364-765X | 0 |
PageRank | References | Authors |
0.34 | 9 | 1 |