MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEOn computing the minimum 3-path vertex cover and dissociation number of graphs
par Frantisek Kardos
| Date : | 24/01/12 | | Time : | 10:30 | | Location : | Galois Coriolis |
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.
Both exact and approximation algorithms for this problem will be presented.
Page des séminaires
| 
