平面グラフの分枝幅決定アルゴリズムの効率的実装

• Item type: SIG Technical Reports(1)
• 公開日: 2006-11-21
• タイトル: 平面グラフの分枝幅決定アルゴリズムの効率的実装
• タイトル / 言語: en
• タイトル: Efficient Implementation of the Algorithm for Computing the Branchwidth of Planar Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 明治大学理工学部情報科学科
• 著者所属: 明治大学理工学部情報科学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Meiji University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Meiji University
• 著者名: 玉木, 久夫; 吉武, 由実
• 著者名(英): Hisao, TAMAKI; Yumi, YOSHITAKE
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面グラフの分枝幅を決定するSeymour と Thomas のアルゴリズムを実装した。その際、このアルゴリズムの背後にあるネズミ捕りゲームの性質を用いた３種類の改良を試みた。改良を実装に組み込んだ結果、メモリ節約が可能となり、素朴な方法で扱うことができなかった辺数の多い例題を扱うことができるようになった。多くの例題で、これまでの研究結果と比べて、この実装が高速であることを確認した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we implement an algorithm of Seymour and Thomas for computing the branchwidth of planar graphs. We propose three improvements based on some observations on the ratcatcher game underlying their algorithm. The improved implementation can save memory usage and deal with the graphs that have too many edges to be dealt with by naive implementations. Experiments show that our implementation is faster on large instances than previously published ones.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2006, 号 122(2006-AL-109), p. 19-26, 発行日 2006-11-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会