For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Note on Irreversible 2-Conversion Sets in Subcubic Graphs
Asahi TAKAOKA Shuichi UENO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/08/01
Online ISSN: 1745-1361
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
feedback vertex set, graphic matroid parity problem, irreversible threshold process, subcubic graphs,
Full Text: PDF>>
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).