D Path Vertex Cover

d-Path Vertex Cover

2018-08-08
Dnes pokračoval Radovan na téma d-PVC. Poznámky a pozorování pro d-liche => modra komponenta spojuje nejvice 2 cervenech vrcholy?? => nelze do ni napojit cerveny vrchol, ktery tvori d+1 cestu s obema cervenyma vrcholama => nejsou modre listy => idea s dominovanim = presunuti do cervenych vrcholu + kazdy vrchol je soucasti nejake d-cesty => idea seznamu vzdalenosti modreho vrcholu od jeho cervenych vrcholů => ale pouze kdyz ty cesty k cervenym vrcholum jsou disjunktni => v tom seznamu kazda dvojice musi presne secist na d ?

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