Dcera Tv

d-Path Vertex Cover

2018-08-08
Dnes mluvil Radovan na téma d-PVC a hitting set. Hitting set vstup: je dán graf a nějaké podmnožiny V(G) F, kde každé je velké nejvýše d. výstup: vybrat co nejméně vrcholů takových, aby bylo pokryté každé F. d-Path Vertex Cover vstup: graf G, $k \in \mathbb{Z}_0^+$, kde $k$ je velikost řešení výstup: $F \subseteq V(G), |F| \leq k$ tedy G \ F takový, aby neobsahoval cestu na d vrcholech