Minimum k-path vertex cover

Abstract : A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by P_k(G) the minimum cardinality of a k-path vertex cover in G. It is shown that the problem of determining P_k(G) is NP-hard for each k ≥ 2, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of P_k(G) and provide several estimations and exact values of P_k(G). We also prove that P_3(G) ≤ (2n + m)/6, for every graph G with n vertices and m edges.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2011, 159 (12), pp.1189-1195. 〈10.1016/j.dam.2011.04.008〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00634981
Contributeur : František Kardoš <>
Soumis le : jeudi 10 novembre 2011 - 09:39:20
Dernière modification le : mardi 14 novembre 2017 - 01:06:47
Document(s) archivé(s) le : jeudi 15 novembre 2012 - 11:41:43

Fichier

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

Identifiants

Collections

Citation

Boštjan Brešar, František Kardoš, Ján Katrenič, Gabriel Semanišin. Minimum k-path vertex cover. Discrete Applied Mathematics, Elsevier, 2011, 159 (12), pp.1189-1195. 〈10.1016/j.dam.2011.04.008〉. 〈inria-00634981〉

Partager

Métriques

Consultations de la notice

161

Téléchargements de fichiers

277