{{ $t("message.ADVERTISEMENT") }}
{{ $t("message.AD_EXPIRE_DATE") }}2024年03月
文献
J-GLOBAL ID:201402299937216758   整理番号:14A1273375

非退化型円弧グラフにおけるフィードバック節点集合問題のための効率的アルゴリズム

An Algorithm for Feedback Vertex Set Problem on a Non-degenerate Circular-arc Graph
著者 (3件):
資料名:
巻: 114  号: 199(COMP2014 15-24)  ページ: 17-22  発行年: 2014年08月26日 
JST資料番号: S0532B  ISSN: 0913-5685  資料種別: 会議録 (C)
記事区分: 原著論文  発行国: 日本 (JPN)  言語: 日本語 (JA)
抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ある節点集合FをグラフGから削除すると,元のグラフGに1つも閉路が存在しないならば,この削除した節点集合Fをフィードバック節点集合とよぶ。フィードバック節点集合の中で,位数最小の節点集合を求める問題をフィードバック節点集合問題といい,この問題は同期システム制御やコンピュータシステム,VLSI回路設計などの分野で応用されている。フィードバック節点集合は単純グラフにおいてNP困難であるが,一般的にNP完全問題は対象とするグラフモデルのクラスを制限することで,効率的に解くことが可能となりえる場合も存在することが知られている。本研究では,対象とするグラフを交差グラフの一種である,非退化型円弧グラフに限定して,同問題を計算量O(n+m)時間で解く効率的なアルゴリズムを与える。(著者抄録)
シソーラス用語:
シソーラス用語/準シソーラス用語
文献のテーマを表すキーワードです。
部分表示の続きはJDreamⅢ(有料)でご覧いただけます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。

準シソーラス用語:
シソーラス用語/準シソーラス用語
文献のテーマを表すキーワードです。
部分表示の続きはJDreamⅢ(有料)でご覧いただけます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。

分類 (1件):
分類
JSTが定めた文献の分類名称とコードです
計算理論 
引用文献 (14件):

前のページに戻る