コーダルグラフの独立点集合の数えあげ問題

• Item type: SIG Technical Reports(1)
• 公開日: 2004-07-27
• タイトル: コーダルグラフの独立点集合の数えあげ問題
• タイトル / 言語: en
• タイトル: Counting the Independent Sets of a Chordal Graph
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Institute of Theoretical Computer Science Department of Computer Science ETH Zürich Switzerland./Supported by Berlin/Zurich Graduate Program Combinatorics Geometry and Computation (CGC)" financed by ETH Zurich and the German Science Foundation (DFG).
• 著者所属: 国立情報学研究所
• 著者所属: 駒澤大学自然科学教室
• 著者所属(英): en
• 著者所属(英): Institute of Theoretical Computer Science, Department of Computer Science, ETH Z&uuml
• 著者所属(英): en
• 著者所属(英): rich, Switzerland/Supported by Berlin/Zurich Graduate Program Combinatorics, Geometry, and Computation (CGC)" financed by ETH Zurich and the German Science Foundation (DFG).
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Komazawa University, Natural Science Faculty
• 著者名: 岡本, 吉央; 宇野, 毅明; 上原, 隆平
• 著者名(英): Yoshio, Okamoto; Takeaki, Uno; Ryuhei, Uehara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: コーダルグラフの独立点集合の数えあげや列挙について研究した．まず，以下の結果をえた．(1)独立点集合の個数を数える線形時間アルゴリズム(2)最大独立点集合の個数を数える線形時間アルゴリズム(3)与えられたサイズの独立点集合を数える多項式時間アルゴリズム．また，これらの列挙が，一つあたりのならし計算量O(1)で可能であることを示した．一方，以下の問題は#P完全であることを示した．(1)極大独立点集合の数えあげ問題(2)要素数最小の極大独立点集合の数えあげ問題．さらに，重み最小の極大独立点集合を見つける問題がNP困難で，かつ近似も困難であることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We provide for a chordal graph (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. On the contrary, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we show that enumerations (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant amortized time per output, while finding a minimum weight maximal independent set in a chordal graph is NP-hard, and even hard to approximate.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2004, 号 76(2004-AL-096), p. 17-24, 発行日 2004-07-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会