| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Minimum k-path vertex cover
Avtorji:Brešar, Boštjan (Avtor)
Kardoš, František (Avtor)
Katrenič, Ján (Avtor)
Semanišin, Gabriel (Avtor)
Datoteke:URL http://dx.doi.org/10.1016/j.dam.2011.04.008
 
Jezik:Angleški jezik
Vrsta gradiva:Delo ni kategorizirano (r6)
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
UDK:519.17
COBISS_ID:15929689 Povezava se odpre v novem oknu
ISSN pri članku:0166-218X
NUK URN:URN:SI:UM:DK:8F1IQIOG
Število ogledov:364
Število prenosov:4
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

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 Novo okno

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
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici