Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs

DOI10.1007/978-3-319-19647-3_26MaRDI QIDQ3452575zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Shaowei Kou

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

zbMATH Keywords

dynamic programmingexact algorithmsgraph algorithms3-path vertex coverdissociation number

Mathematics Subject Classification ID

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)

Recommendations

• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• Complexity of dissociate set problems in some hereditary classes of graphs
• 3-path vertex cover and dissociation number of hexagonal graphs

Cites work

• scientific article; zbMATH DE number 2192124 (Why is no real title available?)
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• A note on the complexity of minimum dominating set
• Algorithms for maximum independent sets
• An improved exact algorithm for maximum induced matching
• An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs
• Complexity and kernels for bipartition into degree-bounded induced graphs
• Exact Algorithms for Maximum Independent Set
• Exact algorithms for dominating set
• Exact exponential algorithms.
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Improper coloring of unit disk graphs
• Independent packings in structured graphs
• Minimum \(k\)-path vertex cover
• NP-hard graph problems and boundary classes of graphs
• Node-Deletion Problems on Bipartite Graphs
• On \({\mathcal F}\)-independence in graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the vertex \(k\)-path cover
• Some results on graphs without long induced paths
• The complexity of dissociation set problems in graphs
• The complexity of restricted spanning tree problems

Cited in

(6)

• A faster FPT algorithm for 3-path vertex cover
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• PTAS for minimum \(k\)-path vertex cover in ball graph
• 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

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)