On computing the minimum 3-path vertex cover and dissociation number of graphs
From MaRDI portal
Publication:650941
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
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (60)
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 coverP4problem 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
