ダウンロード数: 186
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| transinf.2014FCP0012.pdf | 1.04 MB | Adobe PDF | 見る/開く |
| タイトル: | Some Reduction Procedure for Computing Pathwidth of Undirected Graphs |
| 著者: | IKEDA, Masataka NAGAMOCHI, Hiroshi  |
| 著者名の別形: | 永持, 仁 |
| キーワード: | pathwidth exact algorithms graphs chemical graphs |
| 発行日: | 1-Mar-2015 |
| 出版者: | Institute of Electronics, Information and Communication Engineers(IEICE) |
| 誌名: | IEICE Transactions on Information and Systems |
| 巻: | E98.D |
| 号: | 3 |
| 開始ページ: | 503 |
| 終了ページ: | 511 |
| 抄録: | Computing an invariant of a graph such as treewidth and pathwidth is one of the fundamental problems in graph algorithms. In general, determining the pathwidth of a graph is NP-hard. In this paper, we propose several reduction methods for decreasing the instance size without changing the pathwidth, and implemented the methods together with an exact algorithm for computing pathwidth of graphs. Our experimental results show that the number of vertices in all chemical graphs in NCI database decreases by our reduction methods by 53.81% in average. |
| 著作権等: | © 2015 The Institute of Electronics, Information and Communication Engineers |
| URI: | http://hdl.handle.net/2433/196656 |
| DOI(出版社版): | 10.1587/transinf.2014FCP0012 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。