Graph sandwich problem とは

グラフ理論とコンピュータサイエンスでは、グラフサンドイッチ問題は、グラフの特定のファミリに属し、他の2つのグラフの間に「サンドイッチ」されたグラフを見つける問題です。その1つはサブグラフでなければならず、もう1つはグラフでなければなりません所望のグラフのスーパーグラフ。
グラフサンドイッチ問題は、与えられたグラフが一群のグラフに属するかどうかをテストする問題を一般化し、アプリケーションのためおよび認識問題の自然な一般化として注目を集めています。