Minimum k-path vertex cover

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

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	Minimum k-path vertex cover
Avtorji:	ID Brešar, Boštjan (Avtor) ID Kardoš, František (Avtor) ID Katrenič, Ján (Avtor) ID Semanišin, Gabriel (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.dam.2011.04.008
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	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
Leto izida:	2011
Št. strani:	str. 1189-1195
Številčenje:	Vol. 159, iss. 12
PID:	20.500.12556/DKUM-51880
UDK:	519.17
COBISS.SI-ID:	15929689
ISSN pri članku:	0166-218X
NUK URN:	URN:SI:UM:DK:8F1IQIOG
Datum objave v DKUM:	10.07.2015
Število ogledov:	1284
Število prenosov:	24
Metapodatki:
Področja:	Ostalo
:	BREŠAR, Boštjan, KARDOŠ, František, KATRENIČ, Ján in SEMANIŠIN, Gabriel, 2011, Minimum k-path vertex cover. Discrete applied mathematics [na spletu]. 2011. Vol. 159, no. 12, p. 1189–1195. [Dostopano 22 marec 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.dam.2011.04.008 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Iščem podobna dela... Prosim, počakajte...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	Discrete applied mathematics
Skrajšan naslov:	Discrete appl. math.
Založnik:	Elsevier
ISSN:	0166-218X
COBISS.SI-ID:	25342464

Sekundarni jezik

Jezik:	Angleški jezik
Naslov:	Najmanjše po poteh k-vozliščno pokritje
Opis:	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.

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj