• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

A polynomial-time algorithm of finding a minimum k-path vertex cover and a maximum k-path packing in some graphs

Optimization Letters. 2019. P. 1-6.

For a graph G and a positive integer k, a subset C of vertices of G is called a k-path vertex cover if C intersects all paths of k vertices in G. The cardinality of a minimum k-path vertex cover is denoted by β_{P_k}(G). For a graph G and a positive integer k, a subset M of pairwise vertex-disjoint paths of k vertices in G is called a k-path packing. The cardinality of a maximum k-path packing is denoted by μ_{P_k}(G). In this paper, we describe some graphs, having equal values of β_{P_k} and μ{P_k}, for k≥5, and present polynomial-time algorithms of finding a minimum k-path vertex cover and a maximum k-path packing in such graphs.