次数指定した最大正則誘導部分グラフ探索問題(一般)

書誌事項

タイトル別名
  • Finding Maximum Regular Induced Subgraphs with Prescribed Degree

この論文をさがす

説明

本稿では,グラフG=(V, E)と指定次数γが与えられたとき,頂点部分集合S によって誘導される部分グラフG[S]が指定した次数rの正則グラフであり,頂点数が最大となるようなSを見つけ出す最適化問題を考える.また,グラフG[S]がr-正則,かつ連結グラフである場合についても考える.両問題は,ある定数rについて,近似することさえNP困難であることが知られている.本稿では,入力を特別なグラフクラスに限定した問題について考える.rをある定数とし,入力グラフを二部グラフまたは平面グラフに限定したとしても,本稿で考える連結性を条件とする正則誘導連結部分グラフ探索問題と必要としない正則誘導部分グラフ探索問題が近似することさえNP困難のままであることを示す.一方,以下のような木構造を持つグラフを入力とした場合には,両問題が簡単になることを示す.まず,木幅限定グラフを入力としたとき,両問題に対する最適解を線形時間で求めるアルゴリズムを示す.ここで,計算時間に隠れている係数は木幅の単一指数である.更に,入力を弦グラフとしたときには,両問題の最適解を多項式時間で求めることができることを示す.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1572543027742045952
  • NII論文ID
    110009820598
  • NII書誌ID
    AN10013152
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ