アルゴリズムと応用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/10 18:35 UTC 版)
「カクタスグラフ」の記事における「アルゴリズムと応用」の解説
任意のグラフに対してはNP困難である施設配置問題などの問題は、カクタスに対しては多項式時間で解くことができる。 カクタスは外平面グラフの特殊な例であるため、多数のグラフの組合せ最適化問題を多項式時間で解くことができる。 カクタスを用いた電気回路の解析は有用な特徴を持つ。オペアンプをカクタスを用いて解析する応用がなされた。 カクタスは、異なるゲノム間またはゲノムの部分間の関係の表現方法として、比較ゲノミクスの分野で用いられている。 もしカクタスの各頂点が高々2つのブロックにしか属さない場合、そのグラフをクリスマスカクタスと呼ぶ。多面体グラフ（polyhedral graph）はその頂点全てを用いるクリスマスカクタスを部分グラフとして持つ。これは、多面体グラフがユークリッド平面にgreedy embeddingを持ち、任意の頂点間でのルーティングが、greedy forwardingによって成功するというLeighton & Moitra (2010)の証明において重要な役割を果たした。 トポロジカルグラフ理論では、cellar embeddingが「平面」であるグラフは、各頂点が高々1つの閉路にしか含まれないカクタスの部分族である。これらのグラフ族は、ダイヤモンドグラフと5頂点フレンドシップグラフという2つの禁断マイナーを持つ。
※この「アルゴリズムと応用」の解説は、「カクタスグラフ」の解説の一部です。
「アルゴリズムと応用」を含む「カクタスグラフ」の記事については、「カクタスグラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「アルゴリズムと応用」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- アルゴリズムと応用のページへのリンク
