On computing the minimum 3-path vertex cover and dissociation number of graphs
type: Item
instance of: scholarly article
title: On computing the minimum 3-path vertex cover and dissociation number of graphs
zbMATH Open document ID: 1227.68034
author: František Kardoš
author: Ján Katrenič
author: Ingo Schiermeyer
published in: Theoretical Computer Science
publication date: 2011-12-07T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5987018
zbMATH Keywords: path vertex cover
zbMATH Keywords: dissociation number
zbMATH Keywords: approximation
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.09.009
OpenAlex ID: W2034112762
cites work: NP-hard graph problems and boundary classes of graphs
cites work: Q5463498
cites work: Minimum \(k\)-path vertex cover
cites work: Independent packings in structured graphs
cites work: Improved upper bounds for vertex cover
cites work: Introduction to algorithms
cites work: On the hardness of approximating minimum vertex cover
cites work: Exact exponential algorithms.
cites work: Iterative compression and exact algorithms
cites work: On F-independence in graphs
cites work: A fine-grained analysis of a simple independent set algorithm
cites work: Q5530470
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: Node-Deletion Problems on Bipartite Graphs
DOI: 10.1016/J.TCS.2011.09.009
description: scientific article; zbMATH DE number 5987018