On Weighted Perfect Target Set Selection
| Autor: | Mu-Jung Tsai, 蔡牧融 |
|---|---|
| Rok vydání: | 2017 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 105 Consider the following graph process on a strongly connected directed graph G=(V,E) with positive indegrees, a weight function w:V→(0,∞) and a threshold function ϕ:V→[0,∞). At first, we open some vertices of G. Next, each vertex v∈V will be opened when the sum of the weights of its open in-neighbors reaches ϕ(v). The process continues until no more vertices can be opened. We show that if ϕ(v)=(k⁄((k+1) ))⋅〖"deg" 〗^-〖(v)〗 for all v∈V, where k∈Z^+, then there exists a set of no more than (k⁄((k+1) ))⋅|V| vertices whose opening will open all vertices eventually. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|