On computing the minimum 3-path vertex cover and dissociation number of graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2011

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

Résumé

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.
Fichier principal
Vignette du fichier
KKS11.pdf (184.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00635945 , version 1 (10-11-2011)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More