Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
From MaRDI portal
Publication:507444
DOI10.1016/j.tcs.2016.04.043zbMath1357.05146OpenAlexW2412257713MaRDI QIDQ507444
Publication date: 6 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.043
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (22)
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 ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ New Results on Directed Edge Dominating Set ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ The maximum number of maximum dissociation sets in trees ⋮ The k‐path vertex cover: General bounds and chordal graphs ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Maximum weight t-sparse set problem on vector-weighted 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 maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ The geodesic-transversal problem ⋮ 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 ⋮ Unnamed Item ⋮ Parameterized algorithm for 3-path vertex cover ⋮ Relating dissociation, independence, and matchings
Cites Work
- Unnamed Item
- Exact algorithms for dominating set
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- Exact exponential algorithms.
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- Isolation concepts for efficiently enumerating dense subgraphs
- An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs
- A faster FPT algorithm for 3-path vertex cover
- Some results on graphs without long induced paths
- Minimum \(k\)-path vertex cover
- The complexity of dissociation set problems in graphs
- On the vertex \(k\)-path cover
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- A note on the complexity of minimum dominating set
- NP-hard graph problems and boundary classes of graphs
- Independent packings in structured graphs
- Exact Algorithms for Maximum Independent Set
- Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
- An Improved Exact Algorithm for Maximum Induced Matching
- Improper coloring of unit disk graphs
- A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
- On F-independence in graphs
- Algorithms for maximum independent sets
- Node-Deletion Problems on Bipartite Graphs
- The complexity of restricted spanning tree problems
This page was built for publication: Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
