Minimum k-path vertex cover

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2011
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	15929689
ISSN:	0166-218X
Views:	47
Downloads:	20
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Najmanjše po poteh k-vozliščno pokritje
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;algoritem;vozliščno pokritje;pot;NP-polnost;disociacijsko število;po poteh vozliščno pokritje;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 1189-1195
Volume:	Vol. 159
Issue:	iss. 12
Chronology:	2011
ID:	1475487