A Note on Irreversible 2-Conversion Sets in Subcubic Graphs
-
- TAKAOKA Asahi
- Department of Communications and Computer Engineering, Tokyo Institute of Technology
-
- UENO Shuichi
- Department of Communications and Computer Engineering, Tokyo Institute of Technology
書誌事項
- 公開日
- 2015
- 資源種別
- journal article
- DOI
-
- 10.1587/transinf.2015edl8021
- 公開者
- 一般社団法人 電子情報通信学会
この論文をさがす
説明
Irreversible k-conversion set is introduced in connection with the mathematical modeling of the spread of diseases or opinions. We show that the problem to find a minimum irreversible 2-conversion set can be solved in O(n2log 6n) time for graphs with maximum degree at most 3 (subcubic graphs) by reducing it to the graphic matroid parity problem, where n is the number of vertices in a graph. This affirmatively settles an open question posed by Kyncl et al. (2014).
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E98.D (8), 1589-1591, 2015
一般社団法人 電子情報通信学会
関連未分類成果物
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1390282679354555008
-
- NII論文ID
- 130005090406
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 10258/00010201
-
- 本文言語コード
- en
-
- 資料種別
- journal article
-
- データソース種別
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
- KAKEN
- OpenAIRE
-
- 抄録ライセンスフラグ
- 使用不可
