On computing the minimum 3-path vertex cover and dissociation number of graphs

DOI10.1016/j.tcs.2011.09.009zbMath1227.68034MaRDI QIDQ650941

František Kardoš, Ingo Schiermeyer, Ján Katrenič

Publication date: 7 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.009

zbMATH Keywords

approximation; dissociation number; path vertex cover

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Uniformly dissociated graphs, König Graphs with Respect to the 4-Path and Its Spanning Supergraphs, Unnamed Item, Approximating Partially Bounded Degree Deletion on Directed Graphs, Approximating Bounded Degree Deletion via Matroid Matching, Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover, Kernelization of the 3-path vertex cover problem, 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 faster FPT algorithm for 3-path vertex cover, Moderately exponential time algorithms for the maximum bounded-degree-1 set 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, Efficient algorithm for the vertex cover \(P_k\) problem on cacti, Fixed-parameter algorithms for Vertex Cover \(P_3\), 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 (connected) bounded-degree deletion problem on unit disk graphs, Approximation algorithm for minimum weight connected-\(k\)-subgraph cover, Algorithm for online 3-path vertex cover, Parameterized algorithm for 3-path vertex cover, The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs, The \(k\)-path vertex cover of rooted product 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, 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, A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion, Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Improved upper bounds for vertex cover
• On the hardness of approximating minimum vertex cover
• Some results on graphs without long induced paths
• Iterative compression and exact algorithms
• 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 F-independence in graphs
• Node-Deletion Problems on Bipartite Graphs
• The complexity of restricted spanning tree problems