グラフクラスにおける森の数え上げに対する高速指数時間アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2006-05-18
• タイトル: グラフクラスにおける森の数え上げに対する高速指数時間アルゴリズム
• タイトル / 言語: en
• タイトル: Fast Exponential-Time Algorithms for the Forest Counting in Graph Classes
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: スイス連邦工科大学チューリッヒ校情報科学部
• 著者所属: 豊橋技術科学大学情報工学系
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, ETH Zurich
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Science, Toyohashi University of Technology
• 著者名: ハイディ・ゲバウアー; 岡本, 吉央
• 著者名(英): Heidi, Gebauer; Yoshio, Okamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 正則グラフと弦グラフにおける森の数え上げ問題が＃Ｐ完全であることを証明する。また、この問題に対して、３正則グラフにおけるＯ（1.8494m）時間アルゴリズムと単位区間グラフにおけるＯ（1.9706m）時間アルゴリズムを与える。ただし、mはグラフの辺数である。これらのアルゴリズムはTutte多項式の計算へ拡張できる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We prove the #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in Ｏ(1.8494m) time for 3-regular graphs, and Ｏ(1.9706m) time for unit interval graphs, where m is the number of edges in the graph. The algorithms can be generalized to the Tutte polynomial computation.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2006, 号 49(2006-AL-106), p. 57-64, 発行日 2006-05-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会