Minimum k-path vertex cover

Boštjan Brešar (Avtor), František Kardoš (Avtor), Ján Katrenič (Avtor), Gabriel Semanišin (Avtor)

Povzetek

Podmnožica ▫$S$▫ množice vozlišč grafa ▫$G$▫ se imenuje po poteh ▫$k$▫-vozliščno pokritje, če vsaka pot reda ▫$k$▫ v grafu ▫$G$▫ vsebuje vsaj eno vozlišče iz ▫$S$▫. Označimo s ▫$\psi_k(G)$▫ najmanjšo kardinalnost po poteh ▫$k$▫-vozliščnega pokritja v grafu ▫$G$▫. V članku dokažemo, da je problem določitve ▫$\psi_k(G)$▫ NP-poln problem za vsak ▫$k \geq 2$▫, medtem ko lahko za drevesa ta problem rešimo v linearnem času. Raziskujemo zgornje meje za vrednost ▫$\psi_k(G)$▫ in dokažemo več ocen ter točnih vrednosti za to število. Prav tako dokažemo, da je ▫$\psi_3(G) \leq (2n + m)/6$▫, za vsak graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami.

Ključne besede

matematika;teorija grafov;algoritem;vozliščno pokritje;pot;NP-polnost;disociacijsko število;po poteh vozliščno pokritje;mathematics;graph theory;algorithm;path;vertex cover;dissociation number;path vertex cover;NP-complete;

Podatki

Jezik:	Angleški jezik
Leto izida:	2011
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17
COBISS:	15929689
ISSN:	0166-218X
Št. ogledov:	47
Št. prenosov:	20
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Najmanjše po poteh k-vozliščno pokritje
Sekundarni povzetek:	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 ▫$\psi_k(G)$▫ the minimum cardinality of a ▫$k$▫-path vertex cover in ▫$G$▫. It is shown that the problem of determining ▫$\psi_k(G)$▫ is NP-hard for each ▫$k \geq 2$▫, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of ▫$\psi_k(G)$▫ and provide several estimations and exact values of ▫$\psi_k(G)$▫. We also prove that ▫$\psi_3(G) \leq (2n + m)/6$▫, for every graph ▫$G$▫ with ▫$n$▫ vertices and ▫$m$▫ edges.
Sekundarne ključne besede:	matematika;teorija grafov;algoritem;vozliščno pokritje;pot;NP-polnost;disociacijsko število;po poteh vozliščno pokritje;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1189-1195
Letnik:	Vol. 159
Zvezek:	iss. 12
Čas izdaje:	2011
ID:	1475487