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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2011, 412 (50), pp.7009-7017. 〈10.1016/j.tcs.2011.09.009〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00635945
Contributeur : František Kardoš <>
Soumis le : jeudi 10 novembre 2011 - 09:38:14
Dernière modification le : jeudi 27 mars 2014 - 10:57:26
Document(s) archivé(s) le : jeudi 15 novembre 2012 - 11:41:50

Fichier

KKS11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de
la notice

152

Téléchargements du document

195