Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
type: Item
instance of: scholarly article
title: Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
zbMATH Open document ID: 1357.05146
author: Mingyu Xiao
author: Shaowei Kou
published in: Theoretical Computer Science
publication date: 2017-02-06T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6680877
zbMATH Keywords: exact algorithm
zbMATH Keywords: graph algorithm
zbMATH Keywords: dissociation number
zbMATH Keywords: 3-path vertex cover
zbMATH Keywords: dynamic programming
MaRDI profile type: Publication
full work available at URL: j.tcs.2016.04.043
OpenAlex ID: W2412257713
cites work: NP-hard graph problems and boundary classes of graphs
cites work: An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs
cites work: Q5463498
cites work: On the vertex \(k\)-path cover
cites work: Minimum \(k\)-path vertex cover
cites work: Independent packings in structured graphs
cites work: Exact exponential algorithms.
cites work: On F-independence in graphs
cites work: A note on the complexity of minimum dominating set
cites work: Improper coloring of unit disk graphs
cites work: Finding a minimum path cover of a distance-hereditary graph in polynomial time
cites work: On computing the minimum 3-path vertex cover and dissociation number of graphs
cites work: A faster FPT algorithm for 3-path vertex cover
cites work: Isolation concepts for efficiently enumerating dense subgraphs
cites work: Some results on graphs without long induced paths
cites work: The complexity of dissociation set problems in graphs
cites work: The complexity of restricted spanning tree problems
cites work: Algorithms for maximum independent sets
cites work: Exact algorithms for dominating set
cites work: A fixed-parameter algorithm for the vertex cover \(P_3\) problem
cites work: A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
cites work: Exact Algorithms for Maximum Independent Set
cites work: Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
cites work: An Improved Exact Algorithm for Maximum Induced Matching
cites work: Node-Deletion Problems on Bipartite Graphs
DOI: 10.1016/J.TCS.2016.04.043
Recommended article: Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
Recommended article: On computing the minimum 3-path vertex cover and dissociation number of graphs
Recommended article: Approximation algorithms for minimum weight connected 3-path vertex cover
Recommended article: Approximation algorithm for minimum connected 3-path vertex cover
Recommended article: Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
Recommended article: Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
Recommended article: Fixed-parameter algorithms for Vertex Cover \(P_3\)
Recommended article: Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
Recommended article: An exact algorithm for the maximal covering problem
Recommended article: A fixed-parameter algorithm for the vertex cover \(P_3\) problem
description: scientific article; zbMATH DE number 6680877