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(n(2) log(6) n) 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
巻
E98D
号
8
ページ
1589 - 1591
発行年
2015
出版者
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG