A Note on Irreversible 2-Conversion Sets in Subcubic Graphs

	日本語 \| English

▶ 研究成果の引用やURL保存にあたっては、個々のアイテムのページ右上に表示されている「Permalink : http://hdl.handle.net/10258/xxxx」をお使いください。

室蘭工業大学の研究成果を検索・閲覧・ダウンロードできます


	トップ


	ランキング

インデックス

Permalink : http://hdl.handle.net/10258/00010201

File / Name	License
IEICETIS_98_8_1589_1591
IEICETIS_98_8_1589_1591 (79.37KB) [ 8 downloads ]

アイテムタイプ	学術雑誌論文 / Journal Article.
言語	英語
キーワード	feedback vertex set, graphic matroid parity problem, irreversible threshold process, subcubic graphs
著者	TAKAOKA Asahi UENO Shuichi
著者（別表記）	髙岡旭上野修一
室蘭工業大学研究者データベースへのリンク	髙岡旭（TAKAOKA Asahi）
抄録	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
出版者版へのリンク	10.1587/transinf.2015EDL8021
DOI	info:doi/10.1587/transinf.2015EDL8021
日本十進分類法	548
ISSN	1745-1361
権利	Copyright © 2015 IEICE
参考URL	IEICE Transactions Online TOP
著者版フラグ	publisher
フォーマット	application/pdf

-		本アーカイブに登録されているアイテムの著作権は、執筆者、出版社（学協会）などが有します。
-		本アーカイブに登録されているアイテムは、著作権法に規定されている私的使用や引用などの範囲内で利用してください。
-		著作権法に規定されている範囲を超える利用を行う場合には、著作権者の許諾を得てください。

室蘭工業大学附属図書館学術情報係
- 〒050-8585 北海道室蘭市水元町27-1
- TEL 0143-46-5191
- E-Mail gakujo@mmm.muroran-it.ac.jp

COUNTER