Minimum k-path vertex cover

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

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Minimum k-path vertex cover
Authors:	ID Brešar, Boštjan (Author) ID Kardoš, František (Author) ID Katrenič, Ján (Author) ID Semanišin, Gabriel (Author)
Files:	http://dx.doi.org/10.1016/j.dam.2011.04.008
Language:	English
Work type:	Not categorized
Typology:	1.01 - Original Scientific Article
Organization:	FNM - Faculty of Natural Sciences and Mathematics
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
Year of publishing:	2011
Number of pages:	str. 1189-1195
Numbering:	Vol. 159, iss. 12
PID:	20.500.12556/DKUM-51880
UDC:	519.17
ISSN on article:	0166-218X
COBISS.SI-ID:	15929689
NUK URN:	URN:SI:UM:DK:8F1IQIOG
Publication date in DKUM:	10.07.2015
Views:	1284
Downloads:	24
Metadata:
Categories:	Misc.
:	BREŠAR, Boštjan, KARDOŠ, František, KATRENIČ, Ján and SEMANIŠIN, Gabriel, 2011, Minimum k-path vertex cover. Discrete applied mathematics [online]. 2011. Vol. 159, no. 12, p. 1189–1195. [Accessed 22 March 2025]. Retrieved from: http://dx.doi.org/10.1016/j.dam.2011.04.008 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

No similar works found

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:	Discrete applied mathematics
Shortened title:	Discrete appl. math.
Publisher:	Elsevier
ISSN:	0166-218X
COBISS.SI-ID:	25342464

Secondary language

Language:	English
Title:	Najmanjše po poteh k-vozliščno pokritje
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.

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back