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

DOI10.1016/j.tcs.2011.09.009zbMath1227.68034OpenAlexW2034112762MaRDI 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

approximationdissociation numberpath vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

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 ⋮ Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ 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 ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ 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 ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk 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 ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ Minimum number of maximal dissociation sets in trees ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Uniformly dissociated graphs ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ 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 ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ 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 ⋮ The geodesic-transversal problem ⋮ Fixed-parameter algorithms for Vertex Cover \(P_3\) ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ 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 ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ Algorithm for online 3-path vertex cover ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ Parameterized algorithm for 3-path vertex cover ⋮ 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 ⋮ General d-position sets ⋮ 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 ⋮ Approximation algorithms for hitting subgraphs

Cites Work

• 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
• A Fine-grained Analysis of a Simple Independent Set Algorithm
• On F-independence in graphs
• Node-Deletion Problems on Bipartite Graphs
• The complexity of restricted spanning tree problems

This page was built for publication: On computing the minimum 3-path vertex cover and dissociation number of graphs