http://swrc.ontoware.org/ontology#Article
A Note on Irreversible 2-Conversion Sets in Subcubic Graphs
en
feedback vertex set
graphic matroid parity problem
irreversible threshold process
subcubic graphs
TAKAOKA Asahi
UENO Shuichi
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
info:doi/10.1587/transinf.2015EDL8021
548
1745-1361
Copyright © 2015 IEICE
https://search.ieice.org/index.html|IEICE Transactions Online TOP
application/pdf