Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
DOI10.1007/978-3-319-19647-3_26zbMATH Open1408.05129OpenAlexW2405505718MaRDI QIDQ3452575FDOQ3452575
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Exact exponential algorithms.
- Minimum \(k\)-path vertex cover
- On the vertex \(k\)-path cover
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- NP-hard graph problems and boundary classes of graphs
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- Some results on graphs without long induced paths
- On F-independence in graphs
- Node-Deletion Problems on Bipartite Graphs
- The complexity of restricted spanning tree problems
- Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
- Algorithms for maximum independent sets
- A note on the complexity of minimum dominating set
- Exact algorithms for dominating set
- Improper coloring of unit disk graphs
- Independent packings in structured graphs
- Exact Algorithms for Maximum Independent Set
- The complexity of dissociation set problems in graphs
- An Improved Exact Algorithm for Maximum Induced Matching
- An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs
Cited In (5)
This page was built for publication: Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452575)
