-
- ARAKI Hisashi
- Department of Computer Science and Engineering, Toyohashi University of Technology
-
- FUJITO Toshihiro
- Department of Computer Science and Engineering, Toyohashi University of Technology
-
- INOUE Shota
- Department of Computer Science and Engineering, Toyohashi University of Technology
抄録
Suppose one of the edges is attacked in a graph G, where some number of guards are placed on some of its vertices. If a guard is placed on one of the end-vertices of the attacked edge, she can defend such an attack to protect G by passing over the edge. For each of such attacks, every guard is allowed either to move to a neighboring vertex, or to stay at where she is. The eternal vertex cover number τ∞(G) is the minimum number of guards sufficient to protect G from any length of any sequence of edge attacks. This paper derives the eternal vertex cover number τ∞(G) of such graphs constructed by replacing each edge of a tree by an arbitrary elementary bipartite graph (or by an arbitrary clique), in terms of easily computable graph invariants only, thereby showing that τ∞(G) can be computed in polynomial time for such graphs G.
収録刊行物
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A (6), 1153-1160, 2015
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282681287535616
-
- NII論文ID
- 130005071826
-
- ISSN
- 17451337
- 09168508
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可