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

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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• 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)

• 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
• A faster FPT algorithm for 3-path vertex cover
• Title not available (Why is that?)

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)