Minimum $k$-path vertex cover

DOI10.1016/j.dam.2011.04.008zbMath1223.05224arXiv1012.2088OpenAlexW2052790720MaRDI 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

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Approximation algorithms for minimum (weight) connected $k$-path vertex cover ⋮ Kernelization of the 3-path vertex cover problem ⋮ Approximating Bounded Degree Deletion via Matroid Matching ⋮ Augmenting approach for some maximum set problems ⋮ Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ An efficient polynomial time approximation scheme for the vertex cover $P_3$ problem on planar graphs ⋮ Relief aid provision to en route refugees: multi-period mobile facility location with mobile demand ⋮ Geodesic transversal problem for join and lexicographic product of graphs ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ PTAS for the minimum $k$-path connected vertex cover problem in unit disk graphs ⋮ Unnamed Item ⋮ A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs ⋮ On the König graphs for a 5-path and its spanning supergraphs ⋮ On the vertex cover $P_3$ problem parameterized by treewidth ⋮ Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem ⋮ A $5k$-vertex kernel for 3-path vertex cover ⋮ A bound on the dissociation number ⋮ The maximum number of maximum dissociation sets in trees ⋮ 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 ⋮ On the complexity of the regenerator location problem treewidth and other parameters ⋮ Computing connected-$k$-subgraph cover with connectivity requirement ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ Approximation algorithm for minimum weight connected-$k$-subgraph cover ⋮ Maximum dissociation sets in subcubic trees ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ On the Harary Index of Graphs with Given Dissociation Number ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ Extremal vertex-degree function index with given order and dissociation number ⋮ Minimum number of maximal dissociation sets in trees ⋮ On the maximum number of maximum dissociation sets in trees with given 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 ⋮ 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 ⋮ On the vertex $k$-path cover ⋮ Approximation algorithm for the minimum weight connected $k$-subgraph cover problem ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Generalized transversals, generalized vertex covers and node-fault-tolerance in graphs ⋮ A fixed-parameter algorithm for the vertex cover $P_3$ problem ⋮ Efficient algorithm for the vertex cover $P_k$ problem on cacti ⋮ PTAS for minimum $k$-path vertex cover in ball graph ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes ⋮ A PTAS for minimum weighted connected vertex cover $P_3$ problem in 3-dimensional wireless sensor networks ⋮ The geodesic-transversal problem ⋮ Fixed-parameter algorithms for Vertex Cover $P_3$ ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ 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 ⋮ Kernels for packing and covering problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A simpler PTAS for connected $k$-path vertex cover in homogeneous wireless sensor network ⋮ On a relation between $k$-path partition and $k$-path vertex cover ⋮ Maximum induced matching of hexagonal graphs ⋮ Some variations of perfect graphs ⋮ Strong geodetic cores and Cartesian product graphs ⋮ The k-Observer Problem on d-regular Graphs ⋮ Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ Minimizing the Number of Bootstrappings in Fully Homomorphic Encryption ⋮ Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ Algorithm for online 3-path vertex cover ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Minimal path cover sets and monomial ideals ⋮ Relating dissociation, independence, and matchings ⋮ Colored cut games ⋮ 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 ⋮ 3-path vertex cover and dissociation number of hexagonal graphs ⋮ The $k$-path vertex cover of rooted product graphs ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs ⋮ Vertex cover at distance on $H$-free graphs ⋮ Approximation algorithms for hitting subgraphs

Cites Work

Minimum \(k\)-path vertex cover