Minimum $k$-path vertex cover

DOI10.1016/j.dam.2011.04.008zbMath1223.05224arXiv1012.2088MaRDI QIDQ2275922

František Kardoš, Boštjan Brešar, Ján Katrenič, Gabriel Semanisin

Publication date: 10 August 2011

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

Full work available at URL: https://arxiv.org/abs/1012.2088

zbMATH Keywords

algorithm; path; NP-complete; vertex cover; dissociation number; path vertex cover

Mathematics Subject Classification ID

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Uniformly dissociated graphs, König Graphs with Respect to the 4-Path and Its Spanning Supergraphs, Unnamed Item, The k-Observer Problem on d-regular Graphs, Approximating Partially Bounded Degree Deletion on Directed Graphs, Approximating Bounded Degree Deletion via Matroid Matching, Minimal path cover sets and monomial ideals, Approximation algorithms for minimum (weight) connected $k$-path vertex cover, Kernelization of the 3-path vertex cover problem, Augmenting approach for some maximum set problems, On the weighted $k$-path vertex cover problem, 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, A PTAS for minimum weighted connected vertex cover $P_3$ problem in 3-dimensional wireless sensor networks, On computing the minimum 3-path vertex cover and dissociation number of graphs, A primal-dual approximation algorithm for the vertex cover $P^3$ problem, A simpler PTAS for connected $k$-path vertex cover in homogeneous wireless sensor network, Maximum induced matching of hexagonal graphs, Some variations of perfect graphs, On the complexity of the regenerator location problem treewidth and other parameters, A faster FPT algorithm for 3-path vertex cover, An FPT algorithm for the vertex cover $P_4$ problem, An efficient polynomial time approximation scheme for the vertex cover $P_3$ problem on planar graphs, PTAS for $\mathcal{H}$-free node deletion problems in disk graphs, Generalized transversals, generalized vertex covers and node-fault-tolerance in graphs, Efficient algorithm for the vertex cover $P_k$ problem on cacti, Fixed-parameter algorithms for Vertex Cover $P_3$, Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes, Approximation algorithms for minimum weight connected 3-path vertex cover, A multi-start iterated greedy algorithm for the minimum weight vertex cover $P_3$ problem, Hitting subgraphs in $P_4$-tidy graphs, Approximation algorithm for minimum weight connected-$k$-subgraph cover, Kernels for packing and covering problems, Strong geodetic cores and Cartesian product graphs, Algorithm for online 3-path vertex cover, Partitioning a graph into small pieces with applications to path transversal, 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, The $k$-path vertex cover of rooted product graphs, PTAS for the minimum $k$-path connected vertex cover problem in unit disk graphs, On the vertex cover $P_3$ problem parameterized by treewidth, The vertex cover $P_3$ problem in cubic graphs, On the vertex $k$-path cover, Approximation algorithm for the minimum weight connected $k$-subgraph cover problem, Minimizing the Number of Bootstrappings in Fully Homomorphic Encryption, A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs, Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem, Kernelization and Parameterized Algorithms for 3-Path Vertex Cover, Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs

Cites Work

Minimum \(k\)-path vertex cover