On computing the minimum 3-path vertex cover and dissociation number of graphs
From MaRDI portal
Publication:650941
DOI10.1016/J.TCS.2011.09.009zbMATH Open1227.68034OpenAlexW2034112762MaRDI QIDQ650941FDOQ650941
Authors: František Kardoš, Ján Katrenič, Ingo Schiermeyer 
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
Recommendations
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
- 3-path vertex cover and dissociation number of hexagonal graphs
- Kernelization of the 3-path vertex cover problem
- A bound on the dissociation number
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Paths and cycles (05C38)
Cites Work
- Introduction to algorithms
- Exact exponential algorithms.
- Minimum \(k\)-path vertex cover
- NP-hard graph problems and boundary classes of graphs
- Title not available (Why is that?)
- On the hardness of approximating minimum vertex cover
- Improved upper bounds for vertex cover
- Some results on graphs without long induced paths
- On \({\mathcal F}\)-independence in graphs
- Node-Deletion Problems on Bipartite Graphs
- Title not available (Why is that?)
- The complexity of restricted spanning tree problems
- Iterative compression and exact algorithms
- A fine-grained analysis of a simple independent set algorithm
- Independent packings in structured graphs
- The complexity of dissociation set problems in graphs
Cited In (63)
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- The maximum number of maximum dissociation sets in trees
- Maximum dissociation sets in subcubic trees
- Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
- Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- 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
- On the weighted \(k\)-path vertex cover problem
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- König graphs with respect to the 4-path and its spanning supergraphs
- On the vertex cover \(P_3\) problem parameterized by treewidth
- Efficient algorithm for the vertex cover \(P_k\) problem on cacti
- Approximation algorithms for hitting subgraphs
- Hitting subgraphs in \(P_4\)-tidy graphs
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- Approximation algorithm for minimum connected 3-path vertex cover
- Approximation algorithms for minimum weight connected 3-path vertex cover
- Kernelization of the 3-path vertex cover problem
- The \(k\)-path vertex cover of rooted product graphs
- A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem
- Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
- Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
- The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
- Approximating bounded degree deletion via matroid matching
- On partial descriptions of König graphs for odd paths and all their spanning supergraphs
- Approximating partially bounded degree deletion on directed graphs
- Maximal and maximum dissociation sets in general and triangle-free graphs
- A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
- On a relation between \(k\)-path partition and \(k\)-path vertex cover
- The geodesic-transversal problem
- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
- On the vertex \(k\)-path cover
- The vertex cover \(P_3\) problem in cubic graphs
- Relating the independence number and the dissociation number
- Uniformly dissociated graphs
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Algorithm for online 3-path vertex cover
- Relating dissociation, independence, and matchings
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- A faster FPT algorithm for 3-path vertex cover
- A \(5k\)-vertex kernel for 3-path vertex cover
- General \(d\)-position sets
- Parameterized algorithm for 3-path vertex cover
- The k‐path vertex cover: General bounds and chordal graphs
- Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
- On the König graphs for a 5-path and its spanning supergraphs
- Enumerating maximal dissociation sets in three classes of grid graphs
- 3-path vertex cover and dissociation number of hexagonal graphs
- A bound on the dissociation number
- The weighted \(k\)-path vertex cover problem on series-parallel graphs
- On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number
- Title not available (Why is that?)
- Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
- Minimum number of maximal dissociation sets in trees
- On the maximum number of maximum dissociation sets in trees with given dissociation number
- Analyzing the 3-path vertex cover problem in planar bipartite graphs
This page was built for publication: On computing the minimum 3-path vertex cover and dissociation number of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650941)
