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

DOI10.1007/S11590-019-01475-0MaRDI QIDQ2192977zbMATH OpenOpenAlexFDO

Authors D. B. Mokeev, D. S. Malyshev

Publication date 24 August 2020

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-019-01475-0

zbMATH Keywords

\(k\)-path packing\(k\)-path vertex covercomputational complexity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 4089565
• Minimum \(k\)-path vertex cover
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• On the weighted \(k\)-path vertex cover problem
• On the k-path vertex cover of some graph products

Cites work

• A primal-dual approximation algorithm for the vertex cover P^3 problem
• Boundary graph classes for some maximum induced subgraph problems
• Chain packing in graphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• Formal analysis of security protocols for wireless sensor networks
• Graph packings
• König graphs for 3-paths and 3-cycles
• Node-Deletion Problems on Bipartite Graphs
• On König graphs with respect to P₄
• On the completeness of a generalized matching problem
• On the weighted \(k\)-path vertex cover problem
• Paths, Trees, and Flowers
• The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem

Cited in

(10)

• Complexity of the maximum \(k\)-path vertex cover problem
• On partial descriptions of König graphs for odd paths and all their spanning supergraphs
• The geodesic-transversal problem
• Nontrivial path covers of graphs: existence, minimization and maximization
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• On the minimum vertex k-path cover of trees
• PTAS for minimum \(k\)-path vertex cover in ball graph
• The weighted k-path vertex cover problem on series-parallel graphs
• Concatenated k-path covers
• Partitioning vertices of graphs into paths of the same length

This page was built for publication: A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192977)