Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
From MaRDI portal
Publication:3452575
DOI10.1007/978-3-319-19647-3_26zbMath1408.05129OpenAlexW2405505718MaRDI QIDQ3452575
Publication date: 12 November 2015
Published in: Frontiers in Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-19647-3_26
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
Unnamed Item, PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs, PTAS for minimum \(k\)-path vertex cover in ball graph
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
- An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs
- 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
- On F-independence in graphs
- Algorithms for maximum independent sets
- Node-Deletion Problems on Bipartite Graphs
- The complexity of restricted spanning tree problems
