Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs

DOI10.1007/978-3-319-19647-3_26zbMath1408.05129OpenAlexW2405505718MaRDI QIDQ3452575

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 programminggraph algorithmsexact algorithms3-path vertex coverdissociation number

Mathematics Subject Classification ID

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 (3)

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

This page was built for publication: Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs