On the vertex \(k\)-path cover

DOI10.1016/j.dam.2013.02.024zbMath1286.05076OpenAlexW154393378MaRDI QIDQ2446837

Boštjan Brešar, Andrej Taranenko, Marko Jakovac, Ján Katrenič, Gabriel Semanisin

Publication date: 22 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.02.024

zbMATH Keywords

gridsregular graphsaverage degree\(k\)-path vertex cover

Mathematics Subject Classification ID

Paths and cycles (05C38)

Related Items (37)

Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover ⋮ On the peel number and the leaf-height of Galton–Watson trees ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Unnamed Item ⋮ A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ A bound on the dissociation number ⋮ On the weighted \(k\)-path vertex cover problem ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ Relating the independence number and the dissociation number ⋮ An FPT algorithm for the vertex cover \(P_4\) problem ⋮ Uniformly dissociated graphs ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ The vertex cover \(P_3\) problem in cubic graphs ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ The geodesic-transversal problem ⋮ Fixed-parameter algorithms for Vertex Cover \(P_3\) ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ Kernels for packing and covering problems ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ The k-Observer Problem on d-regular Graphs ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Relating dissociation, independence, and matchings ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs ⋮ General d-position sets ⋮ 3-path vertex cover and dissociation number of hexagonal graphs ⋮ The \(k\)-path vertex cover of rooted product graphs ⋮ Vertex cover at distance on \(H\)-free graphs ⋮ Approximation algorithms for hitting subgraphs

Cites Work

• On computing the minimum 3-path vertex cover and dissociation number of graphs
• Some results on graphs without long induced paths
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• NP-hard graph problems and boundary classes of graphs
• Independent packings in structured graphs
• On maximal paths and circuits of graphs
• On F-independence in graphs
• Node-Deletion Problems on Bipartite Graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: On the vertex \(k\)-path cover