Podmnožica ▫$S$▫ množice vozlišč grafa ▫$G$▫ se imenuje vozliščno pokritje ▫$k$▫-poti, če vsaka pot reda ▫$k$▫ v ▫$G$▫ vsebuje vsaj eno vozlišče iz ▫$S$▫. Kardinalnost najmanjšega vozliščnega ...pokritja ▫$k$▫-poti se imenuje število vozliščnega pokritja ▫$k$▫-poti grafa ▫$G$▫ in ga označimo z ▫$\psi_k(G)$▫. Znano je, da je problem najmanjšega vozliščnega pokritja ▫$k$▫-poti (▫$k$▫-PVCP) NP-poln za vse ▫$k \ge 2$▫. V tem članku obravnavamo uteženo verzijo problema ▫$k$▫-PVCP (▫$k$▫-WPVCP), v kateri so vozlišča utežena, problem pa je poiskati takšno množico z najmanjšo skupno težo v grafu ▫$G$▫, po odstranitvi te množice iz grafa ▫$G$▫ v grafu ne ostane nobena pot ▫$P_k$▫. Problem sta na kratko vpeljala že Tu in Thou (2011), vendar doslej še ni bil podrobneje obravnavan. Predstavimo rešitve in učinkovite algoritme za problem ▫$k$▫-WPVCP v nekaterih posebnih razredih grafov. To naredimo za polne grafe in cikle ter kot najpomembnejši rezultat predstavimo algoritem, ki izračuna število vozliščnega pokritja ▫$k$▫-poti na poljubnem uteženem drevesu s časovno zahtevnostjo ▫$O(k \cdot |V(G)|)$▫.
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
