IEICE TRANSACTIONS on Information
A Note on Irreversible 2-Conversion Sets in Subcubic Graphs
Summary :
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).
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.8 pp.1589-1591
- Publication Date
- 2015/08/01
- Publicized
- 2015/05/14
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2015EDL8021
- Type of Manuscript
- LETTER
- Category
- Fundamentals of Information Systems
Authors
Asahi TAKAOKA
Tokyo Institute of Technology
Shuichi UENO
Tokyo Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Asahi TAKAOKA, Shuichi UENO, "A Note on Irreversible 2-Conversion Sets in Subcubic Graphs" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 8, pp. 1589-1591, August 2015, doi: 10.1587/transinf.2015EDL8021.
Abstract: 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).
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2015EDL8021/_p
Copy
@ARTICLE{e98-d_8_1589,
author={Asahi TAKAOKA, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Information},
title={A Note on Irreversible 2-Conversion Sets in Subcubic Graphs},
year={2015},
volume={E98-D},
number={8},
pages={1589-1591},
abstract={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).},
keywords={},
doi={10.1587/transinf.2015EDL8021},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - A Note on Irreversible 2-Conversion Sets in Subcubic Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 1589
EP - 1591
AU - Asahi TAKAOKA
AU - Shuichi UENO
PY - 2015
DO - 10.1587/transinf.2015EDL8021
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2015
AB - 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).
ER -
English
