弦グラフの一般化と、そのグラフ上での問題の難しさ

• 上原 隆平

  駒沢大学自然科学教室

書誌事項

タイトル別名

• Tractable and Intractable Problems on Generalized Chordal Graphs

抄録

弦(chordal)グラフを弦の長さに関して一般化した。長さがkより大きい閉路が必ず弦をもつものをk-chordalグラフと呼び、このグラフ上でのさまざまな問題の複雑さを研究した。まずkが固定された正整数であるとする。このとき、与えられたグラフがk-chordalであるかどうかを判定する問題は、NCに属する。またこのグラフ上での極大無閉路集合を求める問題は、k=3のときはNCに属し、k>3のときはRNCに属することを示した。次に一般のkを考える。そして一般のグラフ上のNP完全問題が、k=Θ(n^ε)のときでもNP完全になることを示した。またこのとき、上記の判定問題がcoNP完全であることも示した。
A generalized chordal graph is characterized by some positive integer k≥3, and whose each cycle of length greater than k has a chord. Several tractable and intractable problems on a k-chordal graph are considered. When k is a fixed positive integer, the recognition problem for k-chordalness is in NC. On a k-chordal graph, the maximal acyclic set problem is in NC when k=3, and the problem is in RNC for any fixed k>3. Next we turn to the general case. We show that any NP-complete problem on a general graph is also NP-complete on a k-chordal graph even if k=Θ(n^ε). We also show that the recognition problem for k-chordalness is coNP-complete for k=Θ(n^ε).

収録刊行物

• 電子情報通信学会技術研究報告. COMP, コンピュテーション

  電子情報通信学会技術研究報告. COMP, コンピュテーション 98 (685), 1-8, 1999-03-24

  一般社団法人電子情報通信学会

キーワード

• 弦グラフ
• 極大無閉路集合問題
• NC
• RNC
• NP完全
• coNP完全

詳細情報

• CRID: 1571417127330465152
• NII論文ID: 110003191689
• NII書誌ID: AN10013152
• 本文言語コード: en
• データソース種別:
  • CiNii Articles