On computing the minimum 3-path vertex cover and dissociation number of graphs

Abstract : The dissociation number of a graph G is the number of vertices in a maximum size induced subgraph of G with vertex degree at most 1. A k-path vertex cover of a graph G is a subset S of vertices of G such that every path of order k in G contains at least one vertex from S. The minimum 3-path vertex cover is a dual problem to the dissociation number. For this problem, we present an exact algorithm with a running time of O∗(1.5171n) on a graph with n vertices. We also provide a polynomial time randomized approximation algorithm with an expected approximation ratio of 23/11 for the minimum 3-path vertex cover.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00635945
Contributor : František Kardoš <>
Submitted on : Thursday, November 10, 2011 - 9:38:14 AM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM
Document(s) archivé(s) le : Thursday, November 15, 2012 - 11:41:50 AM

File

KKS11.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

František Kardoš, Ján Katrenič, Ingo Schiermeyer. On computing the minimum 3-path vertex cover and dissociation number of graphs. Theoretical Computer Science, Elsevier, 2011, 412 (50), pp.7009-7017. ⟨10.1016/j.tcs.2011.09.009⟩. ⟨inria-00635945⟩

Share

Metrics

Record views

468

Files downloads

366