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-0zbMath1448.90084OpenAlexW2972239162MaRDI QIDQ2192977

Dmitrii Mokeev, Dmitriy 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

computational complexity\(k\)-path vertex cover\(k\)-path packing

Mathematics Subject Classification ID

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

Related Items (2)

The geodesic-transversal problem ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs

Cites Work

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

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