Baker’s technique とは

理論計算機科学では、ベーカーの手法は、平面グラフ上の問題に対する多項式時間近似スキーム(PTAS)を設計する方法です。 Brenda Bakerは1983年の会議で発表し、1994年にACMのジャーナルに発表した。
ベーカーのテクニックのアイデアは、グラフをレイヤーに分割して、各レイヤーで問題を最適に解決し、各レイヤーのソリューションを合理的な方法で組み合わせて実行可能なソリューションにすることです。この技法は、サブグラフ同型、最大独立セット、最小頂点カバー、最小支配セット、最小エッジ支配セット、最大三角マッチングなどの問題に対してPTASを与えている。
Erik Demaine、Fedor Fomin、Hajiaghayi、およびDimitrios Thilikosの二次元性理論とそれを解く単純化分解(Demaine、Hajiaghayi&Kawarabayashi(2005)、Demaine、Hajiaghayi&Kawarabayashi(2011))は、Bakerの手法の適用性を一般化し、プレーングラフ上の膨大な問題、より一般的には有界属グラフなどの固定小数点を除いたグラフ、および1平面グラフなどの未成年者では閉じられていない他のクラスのグラフにも適用されます。