The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] irreversible threshold process(1hit)

1-1hit
  • A Note on Irreversible 2-Conversion Sets in Subcubic Graphs

    Asahi TAKAOKA  Shuichi UENO  

     
    LETTER-Fundamentals of Information Systems

      Pubricized:
    2015/05/14
      Vol:
    E98-D No:8
      Page(s):
    1589-1591

    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).