JAIST Repository >
f. 情報社会基盤研究センター >
f10. 学術雑誌論文等 >
f10-1. 雑誌掲載論文 >

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

タイトル: Linear-time counting algorithms for independent sets in chordal graphs
著者: Okamoto, Y
Uno, T
Uehara, R
キーワード: chordal graph
counting
enumeration
independent set
NP-completeness
#P-completeness
polynomial time algorithm
発行日: 2005
出版者: SPRINGER-VERLAG
誌名: Lecture Notes in Computer Science : including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics
巻: 3787
開始ページ: 433
終了ページ: 444
DOI: 10.1007/11604686_38
抄録: 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: This is the author-created version of Springer Berlin / Heidelberg, Yoshio Okamoto, Takeaki Uno and Ryuhei Uehara, Lecture Notes in Computer Science(Graph-Theoretic Concepts in Computer Science), 3787, 2005, 433-444. The original publication is available at www.springerlink.com, http://www.springerlink.com/content/768430570227u750
URI: http://hdl.handle.net/10119/3276
資料タイプ: author
出現コレクション:f10-1. 雑誌掲載論文 (Journal Articles)

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

ファイル 記述 サイズ形式
S-49.pdf83KbAdobe PDF見る/開く

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

 


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