JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10119/7872

タイトル: Counting the number of independent sets in chordal graphs
著者: Okamoto, Yoshio
Uno, Takeaki
Uehara, Ryuhei
キーワード: Chordal graph
counting
enumeration
independent set
NP-completeness
#P-completeness
polynomial time algorithm
発行日: 2008-06
出版者: Elsevier
誌名: Journal of Discrete Algorithms
巻: 6
号: 2
開始ページ: 229
終了ページ: 242
DOI: 10.1016/j.jda.2006.07.006
抄録: We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms 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. With similar ideas, we show that enumeration (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. On the other hand, 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 also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.
Rights: NOTICE: This is the author's version of a work accepted for publication by Elsevier. Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara, Journal of Discrete Algorithms, 6(2), 2008, 229-242, http://dx.doi.org/10.1016/j.jda.2006.07.006
URI: http://hdl.handle.net/10119/7872
資料タイプ: author
出現コレクション:b10-1. 雑誌掲載論文 (Journal Articles)

このアイテムのファイル:

ファイル 記述 サイズ形式
C11140.pdf165KbAdobe PDF見る/開く

当システムに保管されているアイテムはすべて著作権により保護されています。

 


お問い合わせ先 : 北陸先端科学技術大学院大学 研究推進課図書館情報係