圧倒的なセット

同じグラフの 3 つの支配集合 (赤色)。このグラフの支配数は 2 です。(b) と (c) は、頂点が 2 個の支配集合が存在し、頂点が 1 個だけの支配集合は存在しないことを示しています。

グラフ理論において、グラフ $G$ の支配集合とは、その頂点の部分集合 $Dであり、$ $Gのどの頂点も$ $D$ に含まれるか、または $D$ に隣接頂点を持つような集合である。支配数 $γ($ $G$ $)は、$ $G$ の最小支配集合に含まれる頂点の数である。

支配集合問題は、与えられたグラフ $G$ と入力 $Kに対して$ $γ(G) \leq K$ であるかどうかをテストすることに関する問題であり、計算複雑性理論における古典的なNP 完全決定問題です。^[¹^]したがって、すべてのグラフ $G$ $に対してγ($ $G$ $)$ を計算できる効率的なアルゴリズムは存在しないと考えられています。ただし、効率的な近似アルゴリズムや、特定のグラフクラスに対する効率的な厳密アルゴリズムは存在します。

支配集合は、いくつかの分野で実用的な関心を集めている。無線ネットワークにおいては、支配集合はアドホックモバイルネットワーク内で効率的な経路を見つけるために用いられる。また、文書要約や電力網向けのセキュアシステムの設計にも利用されている。

支配集合は独立集合と密接に関連しています。独立集合は、それが極大独立集合である場合に限り、支配集合でもあります。したがって、グラフ内の任意の極大独立集合は、必然的に最小支配集合でもあります。

正式な定義

無向グラフ $G = (V, E)$ が与えられたとき、頂点のサブセット $D\subseteq V$ は、すべての頂点に対して、支配集合と呼ばれる。 $u\in V\setminus D$ 頂点があります $v\in D$ そのため $\{u,v\}\in E$ 。

すべてのグラフには少なくとも1つの支配集合が存在する。 $D=V=$ すべての頂点の集合を考えると、定義によりDは支配集合である。なぜなら頂点は存在しないからである。 $u\in V\setminus D$ より興味深い課題は、小さな支配集合を見つけることである。G $の$ 支配数は次のように定義される。 $\gamma (G):=\min\{|D|:D{\text{ is a dominating set of }}G\}$ 。

歴史

支配問題は1950年代以降研究されてきたが、支配に関する研究のペースは1970年代半ばに著しく増加した。1972年、リチャード・カープは集合被覆問題が NP完全であることを証明した。これは支配集合問題に直接的な影響を与えた。なぜなら、2つの問題の間には頂点から集合への、および辺から非交点交差への直接的な全単射が存在するからである。これにより、支配集合問題もNP完全であることが証明された。^{[ 2 ]}

アルゴリズムと計算複雑性

集合被覆問題はよく知られたNP困難問題であり、集合被覆の決定版はKarpの21のNP完全問題の1つでした。最小支配集合問題と集合被覆問題の間には、多項式時間L還元のペアが存在します。^[³^]これらの還元（下記参照）は、最小支配集合問題に対する効率的なアルゴリズムが集合被覆問題に対する効率的なアルゴリズムを提供し、その逆もまた同様であることを示しています。さらに、還元は近似比を保持します。任意のαに対して、最小支配集合に対する多項式時間α近似アルゴリズムは、集合被覆問題に対する多項式時間α近似アルゴリズムを提供し、その逆もまた同様です。実際、どちらの問題もLog-APX完全です。^[⁴^]

集合被覆の近似可能性もよく理解されています。単純な貪欲アルゴリズムを使用すれば対数近似係数を見つけることができますが、劣対数近似係数を見つけることはNP困難です。より具体的には、貪欲アルゴリズムは最小支配集合の $1 + log | V |$ 係数近似を提供し、 P = NPでない限り、多項式時間アルゴリズムでは、ある $c$ $> 0に対して$ $c log | V |$ よりも優れた近似係数を達成することはできません。^[⁵^]

L還元

以下の２つの還元は、最小支配集合問題と集合被覆問題が L還元の下で等価であることを示している。一方の問題のインスタンスが与えられた場合、他方の問題の等価なインスタンスを構築することができる。^{[ 3 ]}

セットからセットへと圧倒的なカバー力を発揮

グラフ $G = (V, E)が$ $V = {1, 2, ..., n}$ で与えられたとき、次のように集合被覆インスタンス $(U, S)を構築します。$ 全体集合 $U$ は $V$ であり、部分集合の族は $S = {S 1, S 2, ..., S n}$ で、 $S v$ $はG$ 内の頂点 $v$ と $v$ に隣接するすべての頂点から構成されます。

ここで、 $Dが$ $G$ の支配集合である場合、 $C = {S v : v \in D}$ は集合被覆問題の実行可能解であり、 $| C | = | D |$ となります。逆に、 $C = {S v : v \in D}$ が集合被覆問題の実行可能解である場合、 $Dは$ $G$ の支配集合であり、 $| D | = | C |$ となります。

$したがって、 G$ の最小支配集合のサイズは、 $(U, S)$ の最小集合被覆のサイズと等しくなります。さらに、支配集合を同じサイズの集合被覆にマッピングし、またその逆も行う単純なアルゴリズムが存在します。特に、集合被覆に対する効率的なα 近似アルゴリズムは、最小支配集合に対する効率的なα 近似アルゴリズムを提供します。

例えば、右図に示すグラフ

G

が与えられた場合、全体集合

U = {1, 2, ..., 6}

と部分集合

S 1 = {1, 2, 5}、

S 2 = {1, 2, 3, 5}、

S 3 = {2, 3, 4, 6 }、

S 4 = {3, 4}、S 5 = {1, 2, 5, 6}

、

S

6 =

{

3

, 5, 6} を持つ

集合

被覆インスタンスを構築します。

この例では、

D = {3, 5}は

G

の支配集合であり、これは集合被覆

C = {S 3, S 5} に対応します。

例えば、頂点

4 \in V

は頂点

3 \in D

によって支配され、要素

4 \in U

は集合

S 3 \in C

に含まれています。

セットカバーからセットの支配へ

$(S, U)$ を、 $全体集合$ $U$ と部分集合の族 $S = {S i : i \in I}$ を持つ集合被覆問題のインスタンスとする。Uとインデックス集合 $I$ は互いに素であると仮定する。次のようにグラフ $G$ $= ($ $V$ $,$ $E$ $)$ を構築する。頂点の集合は $V$ $=$ $I$ $\cup$ $U$ であり、各ペア $i$ $,$ $j$ $\in$ $I$ の間にエッジ ${$ $i$ $,$ $j$ $} \in$ $Eが存在し、各$ $i$ $\in$ $I$ と $u$ $\in$ $S$ $i$ の間にもエッジ ${$ $i$ $,$ $u$ $}$ が存在する。つまり、 $Gは$ 分割グラフであり、 $Iは$ クリークであり、 $Uは$ 独立集合である。

ここで、 $C = {S i : i \in D}が、ある部分集合$ $D \subseteq I$ の集合被覆問題の実行可能な解である場合、 $D は$ $G$ の支配集合であり、 $| D | = | C |$ となります。まず、各 $u \in Uに対して、$ $u$ $\in$ $S$ $i$ となる $i \in D$ が存在し、構成上、 $u$ と $iは$ $G$ で隣接しています。したがって、 $uは$ $i$ によって支配されます。次に、 $D は$ 空でない必要があるため、各 $i$ $\in$ $I$ $はD$ の頂点に隣接しています。

逆に、 $D を$ $G$ の支配集合とする。このとき、 $|$ $X$ $|$ $\leq$ $|$ $D$ $|$ かつ $X$ $\subseteq$ $I$ となるような別の支配集合 $Xを構築することができる。各$ $u$ $\in$ $D$ $\cap$ $U を$ $u$ の隣接 $i$ $\in$ $I$ で置き換えるだけでよい。すると、 $C$ $= {$ $S$ $i$ $:$ $i$ $\in$ $X$ $}$ は集合被覆問題の実行可能な解となり、 $|$ $C$ $|$ $=$ $|$ $X$ $|$ $\leq$ $|$ $D$ $|$ となる。

右側の図は、

U = {a, b, c, d, e}、 I = {1, 2, 3, 4}、

S 1 = {a, b, c}、

S 2 = {a, b}、

S 3 = {b, c, d}、

および

S 4 = {c, d, e} の構成を示しています。

この例では、

C = {S 1, S 4}

は集合被覆であり、これは支配集合

D = {1, 4} に対応します。

D = {a, 3, 4}

は、グラフ

G

の別の支配集合です。D が与えられたとき

、

D

より大きくなく、かつ

I

の部分集合である支配集合

X = {1, 3, 4}

を構築できます。支配集合

X

は、集合被覆

C

= {

S

1

,

S

3

,

S

4

} に対応します。

特別なケース

グラフの最大次数が Δ の場合、貪欲近似アルゴリズムは最小支配集合の $O (log Δ)近似を見つけます。また、貪欲近似を使用して得られた支配集合の$ 濃度を $d g$ とすると、次の関係が成り立ちます。 $d_{g}\leq N+1-{\sqrt {2M+1}}$ ここで、 $N$ は与えられた無向グラフのノード数、 $M$ はエッジ数である。^{[ 6 ]}固定 Δ の場合、これはAPXメンバーシップの支配集合として適格であり、実際には APX 完全である。^{[ 7 ]}

この問題には、単位円盤グラフや平面グラフなどの特殊なケースに対して多項式時間近似スキーム（PTAS）が適用可能です。^[⁸^]直並列グラフでは、最小支配集合を線形時間で見つけることができます。^[⁹^]

正確なアルゴリズム

$n$ 頂点グラフの最小支配集合は、すべての頂点部分集合を調べることで $O (2 n n)$ の時間で見つけることができます。Fomin 、Grandoni 、 Kratsch (2009)は、最小支配集合を $O (1.5137 n)の時間で指数空間で、また$ $O (1.5264 n)$ の時間で多項式空間で見つける方法を示しています。より高速なアルゴリズムは、 $O (1.5048 n) の$ 時間を使用するvan Rooij、Nederlof 、 van Dijk (2009)によって発見され、彼らはまた、この時間で最小支配集合の数を計算できることも示しています。最小支配集合の数は最大で $1.7159 n$ $であり、そのようなすべての集合はO (1.7159 n)$ の時間でリストできます。^{[ 10 ]}

パラメータ化された複雑性

$サイズk$ の支配集合を見つけることは、パラメータ化複雑性の理論において中心的な役割を果たします。これはクラスW[2]に対して最もよく知られた完全な問題であり、他の問題の扱いにくさを示す多くの還元で使用されています。特に、この問題は固定パラメータ扱い可能ではありません。つまり、W 階層が FPT=W[2] に縮退しない限り、任意の関数 $fに対して実行時間$ $f (k) n O(1)のアルゴリズムは存在しません。$

一方、入力グラフが平面グラフの場合、問題はNP困難のままですが、固定パラメータアルゴリズムが知られています。実際、この問題は $k$ に線形なサイズのカーネルを持ち、^{[ 11 ]}カーネルの分岐分解に動的計画法を適用することで、√kに指数関数的、 $n$ に3次的な実行時間を得ることができます。^[¹²^]より一般的には、支配集合問題とその多くの変種は、支配集合のサイズと最小の禁止完全二部グラフのサイズの両方でパラメータ化されると、固定パラメータ扱い可能になります。つまり、この問題は、平面グラフを含む非常に一般的な疎グラフのクラスである、バイクリークフリーグラフ上でFPTです。 ^[¹³^]

支配集合の補集合である非遮断集合は、任意のグラフ上で固定パラメータアルゴリズムによって見つけることができる。^{[ 14 ]}

バリエーション

独立支配集合とは、支配集合でありながら独立集合でもある集合、あるいは同等に、極大独立集合のことである。独立支配数 $i(G)$ $はG$ の独立支配集合の最小サイズです。最小値はより少ない集合で取られるため、 $\gamma (G)\leq i(G)$ すべてのグラフ $G$ に対して、不等式は厳密なものになり得る。クローフリーグラフに対しては等号が成り立つ。^{[ 15 ]}すべての線グラフはクローフリーであるため、任意のグラフの最小最大マッチングと最小エッジ支配セットは同じサイズになることがわかる。

グラフの独立支配集合 $G$ は、すべての独立集合を支配する集合である。 $G$ 独立支配数 $i\gamma (G)$ すべての独立集合の中で最大値である。 $A$ の $G$ 最小の集合を支配する $A$ ^{[ 16 ]}独立集合のみを支配するには、すべての頂点を支配するよりも必要な頂点の数が少なくなる可能性があるため、 $i\gamma (G)\leq \gamma (G)$ すべてのグラフについて $G$ 比率 $\gamma (G)/i\gamma (G)$ 任意に大きくすることができる。^{[ 16 ]}

連結支配集合とは、連結でもある支配集合のことです。 $S$ は連結支配集合であり、の全域木を形成できる。 $G$ その中で $S$ は木の非葉頂点の集合を形成します。逆に、 $T$ は、2 つ以上の頂点を持つグラフの全域木であり、その非葉頂点は $T$ 連結支配集合を形成する。したがって、最小連結支配集合を見つけることは、可能な限り最大の葉を持つ全域木を見つけることと同等である。

全支配集合とは、グラフ内のすべての頂点（支配集合内の頂点自身を含む）が、支配集合内に隣接頂点を持つような頂点の集合である。^{[ 17 ]}つまり、すべての頂点に対して、 $u\in V$ 頂点があります $v\in D$ そのため $\{u,v\}\in E$ 上の図(c)は、連結支配集合かつ全支配集合である支配集合を示しています。図(a)と(b)の例はどちらでもありません。単純支配集合とは対照的に、全支配集合は存在しない場合があります。たとえば、1つ以上の頂点を持ち、辺を持たないグラフは、全支配集合を持ちません。全支配数 $\gamma ^{\text{total}}(G)$ $は、 G$ の全支配集合の最小サイズとして定義されます。明らかに、 $\gamma ^{\text{total}}(G)\geq \gamma (G)$ 。

支配エッジ集合とは、その和集合が支配集合となるエッジ（頂点ペア）の集合のことです。このような集合は存在しない場合もあります（例えば、頂点が1つ以上あってエッジが全くないグラフには存在しません）。もし存在するならば、そのすべてのエッジの和集合は完全な支配集合となります。したがって、エッジ支配集合の最小サイズは少なくともです。 $\gamma ^{\text{total}}(G)/2$ 。

対照的に、辺支配集合は集合である $D$ 辺ので、に含まれないすべての辺 $D$ 少なくとも１つの辺に隣接している $D$ ;そのような集合は常に存在する（例えば、すべての辺の集合は辺支配集合である）。

$k$ 支配集合とは、集合に含まれない各頂点が集合内に少なくとも $k 個$ の隣接頂点を持つような頂点の集合です (標準支配集合は 1 支配集合です)。同様に、 $k$ タプル支配集合とは、グラフ内の各頂点が集合内に少なくとも $k 個の$ 隣接頂点を持つような頂点の集合です (全支配集合は 1 タプル支配集合です)。最小 $k$ タプル支配集合の $(1 + log n)$ 近似は多項式時間で見つけることができます。^[¹⁸^]すべてのグラフは $k$ 支配集合 (例えば、すべての頂点の集合) を持ちますが、最小次数が $k$ $- 1のグラフのみが$ $k$ タプル支配集合を持ちます。ただし、グラフが k タプル支配集合を持つ場合でも、最小 $k$ タプル支配集合は同じグラフの最小 k 支配集合の $ほぼ$ $k$ $倍$ の大きさになる可能性があります。 ^[¹⁹^]最小 $k$ 支配集合の $(1.7 + log Δ)$ 近似も多項式時間で見つけることができる。

分数支配集合は、分数支配関数、関数から定義される。 $f:V(G)\to [0,1]$ すべての頂点に対して $v\in V$ 合計 $f$ 閉鎖された地域を越えて $N[v]$ 少なくとも 1 である。^{[ 20 ]}分数支配数 $\gamma _{f}(G)$ は、そのような関数の最小総重み（すべての頂点値の合計）であり、以下を満たす。 $\gamma _{f}(G)\leq \gamma (G)$ . $k$ -通常のグラフ $n$ 頂点（ $k\geq 1$ ）、分数支配数は $n/(k+1)$ 。

スター支配集合は部分集合である $D$ の $V$ すべての頂点に対して $v$ で $V$ のスター $v$ （隣接するエッジのセット） $v$ ) は、ある頂点の星と交差する $D$ 明らかに、もし $G$ 孤立頂点がある場合、スター支配集合は存在しません（孤立頂点のスターは空であるため）。 $G$ 孤立した頂点がない場合、すべての支配集合はスター支配集合であり、その逆もまた然りです。スター支配と通常の支配の区別は、それらの分数変種を考慮するとより顕著になります。^{[ 21 ]}

ドマティック分割とは、頂点を互いに素な支配集合に分割することである。ドマティック数とは、ドマティック分割の最大サイズのことである。

永遠の支配集合は、頂点が $v$ 支配的なセットにおいて $D$ 選ばれて隣人と置き換えられる $u$ （ $u$ は $D$ )修正された $D$ は支配集合でもあり、このプロセスは任意の無限の頂点選択の列に対して繰り返すことができる。 $v$ 。

効率的な支配集合（ed集合または独立完全支配集合とも呼ばれる^{[ 22 ]}）は、グラフのすべての頂点が集合内のちょうど1つの頂点によって支配されるという追加の性質を持つ支配集合である。^{[ 23 ]}

ローマ支配集合は、ローマ支配関数によって定義され、各頂点にから値を割り当てます。 $\{0,1,2\}$ 0が割り当てられたすべての頂点は、2が割り当てられた少なくとも1つの頂点に隣接している。ローマ支配数 $\gamma _{R}(G)$ は、そのようなすべての関数におけるすべての頂点値の合計の最小値です。この概念は、ローマ帝国の防御戦略にヒントを得ており、頂点は都市を表し、値は駐屯している軍団を表します。任意のグラフに対して $G$ 、 $\gamma (G)\leq \gamma _{R}(G)\leq 2\gamma (G)$ 下限は空のグラフによってのみ達成される。^{[ 24 ]}

グローバル支配集合とは、グラフの支配集合のことである。 $G$ それは補グラフの支配集合でもある ${\overline {G}}$ 世界支配数 $\gamma _{g}(G)$ は、グローバル支配集合の最小濃度です。同様に、支配集合は $S$ がグローバル支配集合であるのは、各頂点に対してが成り立つ場合のみである。 $v\in V-S$ 頂点が存在する $u\in S$ そのため $u$ 隣接していません $v$ 定義上、 $\gamma _{g}(G)=\gamma _{g}{\big (}{\overline {G}}{\big )}$ そして $\gamma (G)\leq \gamma _{g}(G)$ グラフの場合 $G$ と $p$ 頂点、 $\gamma _{g}(G)=p$ かつその場合に限り $G=K_{p}$ または $G={\overline {K_{p}}}$ [ ²⁵^]

認定支配集合とは、集合内のすべての頂点が、集合外に0個または少なくとも2個の隣接点を持つ支配集合のことである。^{[ 26 ]}認定支配数 $\gamma _{\text{cer}}(G)$ は、認定された支配集合の最小サイズです。明らかに、 $\gamma _{\text{cer}}(G)\geq \gamma (G)$ 、また、グラフに弱いサポート頂点がない場合（特に、 $\delta (G)\geq 2$ )連結グラフの場合、 $\gamma _{\text{cer}}(G)\leq 2\gamma (G)$ 。

グラフの対になった支配集合 $G=(V,E)$ 支配的な集合である $S$ 誘導部分グラフとなるような頂点 $G[S]$ 少なくとも1つの完全一致を含む。^{[ 27 ]}ペア支配数 $\gamma _{p}(G)$ は、ペアになった支配集合の最小濃度です。 $G$ この概念は、グラフの頂点に警備員を配置してすべての頂点を支配（保護）する状況をモデル化しており、さらに各警備員にはバックアップとして隣接する別の警備員が割り当てられるという制約が加わっています。

その他のバリエーションには

抑制された支配集合、^{[ 28 ]}
支配集合を確保する、^{[ 29 ]}
三重連結支配集合、^{[ 30 ]}
署名された支配セット、^{[ 31 ]}
支配集合を除いた^{[ 32 ]}および
友好的な支配的セット。^{[ 33 ]}

注記

↑ゲイリー＆ジョンソン（1979）。
↑ヘデトニエミとラスカー (1990)。
1 2 Kann (1992)、108 ～ 109 ページ。
↑エスコフィエとパスチョス (2006)。
↑ Raz & Safra (1997)。
↑パレク（1991）。
↑パパディミトリウとヤナカキス (1991)。
↑クレシェンツィら（2000）。
↑高見沢、西関、斉藤 (1982)。
↑ Fomin et al. (2008)。
↑アルバー、フェローズ、ニーダーマイヤー (2004)。
↑ Fomin & Thilikos (2006)。
↑テルとヴィランジェ (2012)。
↑ Dehne et al. (2006)。
↑アラン＆ラスカー（1978）。
1 2アハロニ、ベルガー、ジヴ (2007)。
↑ West (2001)、第 3.1 節。
↑クラーシングとラフォレスト (2004)。
↑フォルスター (2013)。
↑ヘインズ、ヘデトニエミ、スレーター (1998)。
↑メシュラム (2003)。
↑バンゲ、バルカウスカス、スレーター (1988)。
↑ブランドシュテット、ライタート、ラウテンバッハ (2012)。
↑ Cockayne et al. (2004)。
↑サンパスクマール (1989)。
↑ Dettlaff et al. (2020)。
↑ヘインズ＆スレーター（1998）。
↑ドムケら（1999）。
↑メルアン＆チェラリ (2015)。
↑ Mahadevan et al. (2012)。
↑ハース＆ウェクスラー（2004）。
↑カンとシャン (2020)。
↑カバハグジュニア、エバージェ&フェルナンデス (2025)。

参考文献

アハロニ、ロン。バーガー、イーライ。ジヴ、ラン (2007-05-01)。「加重グラフにおける代表者の独立したシステム」。コンビナトリカ。27 (3): 253–267 .土井: 10.1007/s00493-007-2086-y。ISSN 1439-6912。S2CID 43510417。
Alber, Jochen; Fellows, Michael R ; Niedermeier, Rolf (2004)、「支配集合に対する多項式時間データ削減」、Journal of the ACM、51 (3): 363–384、arXiv : cs/0207066、doi : 10.1145/990308.990309、S2CID 488501 。
Allan, Robert B.; Laskar, Renu (1978)、「グラフの支配と独立支配数について」、Discrete Mathematics、23 (2): 73–76、doi : 10.1016/0012-365X(78)90105-X。
Bange, DW; Barkauskas, AE; Slater, PJ (1988). 「グラフにおける効率的な支配集合」.離散数学の応用. フィラデルフィア: SIAM. pp. 189–199 .
Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012). "グラフとハイパーグラフのための効率的な支配集合と辺支配集合". Algorithms and Computation . Lecture Notes in Computer Science. Vol. 7676. Berlin, Heidelberg: Springer. pp. 267–277 . arXiv : 1207.0953 . doi : 10.1007/978-3-642-35261-4_30 . ISBN 978-3-642-35261-4。
Cabahug Jr., IS; Eballe, RG; Fernandez, RT (2025). "グラフにおけるフレンドリー支配" . European Journal of Pure & Applied Mathematics . 18 (4): 1– 15. doi : 10.29020/nybg.ejpam.v18i4.6326 .
Cockayne, EJ; Dreyer, PA; Hedetniemi, SM; Hedetniemi, ST (2004). "グラフにおけるローマ支配". Discrete Mathematics . 278 ( 1–3 ): 11–22 . doi : 10.1016/j.disc.2003.06.004 .
クレッシェンツィ、ピエルルイジ。カン、ヴィゴ。ハルドルソン、マグナス。Karpinski, マレク; Woeginger、Gerhard (2000)、「最小支配集合」、NP 最適化問題の概要。
Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena ; Rosamond, Frances (2006)、「Nonblocker: Parameterized algorithmics for minimum dominating set」（PDF）、SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science、チェコ共和国メリン、2006年1月21日～27日、Proceedings、Lecture Notes in Computer Science、vol. 3831、Springer、pp. 237–245、doi : 10.1007/11611257_21、ISBN 978-3-540-31198-0。
デトラフ、マグダ。レマンスカ、マグダレナ。トップ、ジャージー。ジーマン、ラドスワフ。ジリンスキ、パヴェウ（2020）。「認定された支配」。AKCE グラフと組み合わせ論の国際ジャーナル。17 (1): 86–97。土井: 10.1016/j.akcej.2018.09.004。ISSN 0972-8600。
Domke, Gayla S.; Hattingh, Johannes H.; Hedetniemi, Stephen T.; Laskar, Renu C.; Markus, Lisa R. (1999). "グラフにおける制約付き支配". Discrete Mathematics . 203 ( 1–3 ): 61–69 . doi : 10.1016/S0012-365X(99)00016-3 . ISSN 0012-365X .
エスコフィエ、ブルーノ；パスコス、ヴァンゲリス Th. (2006)、「APXを超える近似クラスの完全性」(PDF)、理論計算機科学、359 ( 1–3 ): 369–377、doi : 10.1016/j.tcs.2006.05.023
Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997)、「爪のないグラフ ― 概説」、Discrete Mathematics、164 ( 1–3 ): 87–147、doi : 10.1016/S0012-365X(96)00045-3、MR 1432221 。
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009)、「厳密アルゴリズムの解析のための測定と征服のアプローチ」、Journal of the ACM、56 (5): 25:1–32、doi : 10.1145/1552285.1552286、S2CID 1186651 。
Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008)、「測度と征服による組み合わせ境界：最小支配集合の境界と応用」、ACM Transactions on Algorithms、5 (1): 9:1–17、doi : 10.1145/1435375.1435384、S2CID 2489447 。
Fomin, Fedor V.; Thilikos, Dimitrios M. (2006)、「平面グラフにおける支配集合：分岐幅と指数関数的高速化」、SIAM Journal on Computing、36 (2): 281、doi : 10.1137/S0097539702419649、hdl : 2117/97398、S2CID 5232238 。
Förster, Klaus-Tycho. (2013), "一般グラフにおける耐障害性支配の近似",第10回解析アルゴリズムと組み合わせ論に関するワークショップANALCO論文集、SIAM、pp. 25–32、doi : 10.1137/1.9781611973037.4、ISBN 978-1-61197-254-2。
ゲイリー、マイケル・R.、ジョンソン、デイビッド・S. (1979).コンピュータと難解性：NP完全性理論への手引き. 数学科学シリーズ（第1 版）. ニューヨーク：WHフリーマン・アンド・カンパニー. ISBN 9780716710455. MR 0519066 . OCLC 247570676 . 、190ページ、問題GT2。
Haas, Ruth; Wexler, Thomas B. (2004). "グラフとその補グラフの符号付き支配数". Discrete Mathematics . 283 ( 1–3 ): 87–92 . doi : 10.1016/j.disc.2004.01.007 . ISSN 0012-365X .
Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J. (1998).グラフにおける支配の基礎. Marcel Dekker. pp. 261–262 . ISBN 9780429157769。
Haynes, Teresa W.; Slater, Peter J. (1998). "グラフにおけるペア支配". Networks . 32 (3): 199–206 . doi : 10.1002/(SICI)1097-0037(199810)32:3 < 199::AID-NET4 > 3.0.CO ; 2-F . ISSN 0028-3045 .
Hedetniemi, ST; Laskar, RC (1990)、「グラフにおける支配に関する文献目録と支配パラメータの基本的な定義」、Discrete Mathematics、86 ( 1–3 ): 257–277、doi : 10.1016/0012-365X(90)90365-O。
Kang, L.; Shan, E. (2020). "グラフにおける符号付きおよびマイナス支配関数". Haynes, TW; Hedetniemi, ST; Henning, MA (編)『グラフにおける支配に関するトピックス』数学の発展、第 64巻、Cham: Springer. doi : 10.1007/978-3-030-51117-3_9 . ISBN 978-3-030-51117-3。
Kann, Viggo (1992)、「NP完全最適化問題の近似可能性について」（PDF）。博士論文、数値解析・計算科学科、王立工科大学、ストックホルム{{citation}}: CS1 maint: postscript (リンク)。
Klasing, Ralf; Laforest, Christian (2004)、「グラフにおけるkタプル支配の困難性結果と近似アルゴリズム」、Information Processing Letters、89 (2): 75–83、doi : 10.1016/j.ipl.2003.10.004。
Mahadevan, G; Avadayappan, S; Joseph, JP; Subramanian, T (2012). "グラフの三重連結支配数". International Journal of Mathematical Combinatorics . 3 : 93–104 .
Merouane, Houcine Boumediene; Chellali, Mustapha (2015). "グラフにおける安全な支配について". Information Processing Letters . 115 (10): 786–790 . doi : 10.1016/j.ipl.2015.05.006 . ISSN 0020-0190 .
Meshulam, Roy (2003-05-01). "支配数とホモロジー" . Journal of Combinatorial Theory, Series A . 102 (2): 321– 330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 .
Papadimitriou, Christos H.; Yannakakis, Mihailis (1991)、「最適化、近似、および複雑性クラス」、Journal of Computer and System Sciences、43 (3): 425–440、doi : 10.1016/0022-0000(91)90023-X
Parekh, Abhay K. (1991)、「グラフにおける小さな支配集合を見つけるための貪欲ヒューリスティックの分析」、Information Processing Letters、39 (5): 237–240、doi : 10.1016/0020-0190(91)90021-9、hdl : 1721.1/1201
Raz, R. ; Safra, S. (1997)、「NPの準定数エラー確率低次数テストと準定数エラー確率PCP特性」、第29回ACM理論計算機科学シンポジウム論文集、ACM、pp. 475–484、doi : 10.1145/258533.258641、ISBN 0-89791-888-6S2CID 15457604 。
Sampathkumar, E. (1989). 「グラフのグローバル支配数」 . Journal of Mathematical and Physical Sciences . 23 (5): 377–385 .
高見沢和也、西関哲也、斎藤直樹（1982）「直並列グラフ上の組合せ問題の線形時間計算可能性」、Journal of the ACM、29（3）：623–641、doi：10.1145/322326.322328、S2CID 16082154 。
Telle, Jan Arne; Villanger, Yngve (2012)、「二部グラフのないグラフにおける支配のためのFPTアルゴリズム」、Epstein, Leah; Ferragina, Paolo (編)、Algorithms – ESA 2012: 20th Annual European Symposium、リュブリャナ、スロベニア、2012年9月10～12日、Proceedings、Lecture Notes in Computer Science、vol. 7501、Springer、pp. 802–812、doi : 10.1007/978-3-642-33090-2_69、ISBN 978-3-642-33089-6。
ヴァン・ローイ、JMM。ネダーロフ、J. van Dijk、TC (2009)、「包含/除外と測定と征服の組み合わせ: 支配的なセットをカウントするための正確なアルゴリズム」、Proc.第 17 回アルゴリズムに関する欧州年次シンポジウム、ESA 2009、コンピュータサイエンスの講義ノート、vol. 5757、Springer、pp. 554–565、土井：10.1007/978-3-642-04128-0_50、ISBN 978-3-642-04127-3。

さらに読む

Grandoni, F. (2006)、「最小支配集合の複雑性に関する注記」、Journal of Discrete Algorithms、4 (2): 209–214、CiteSeerX 10.1.1.108.3223、doi : 10.1016/j.jda.2005.03.002 。
Guha, S.; Khuller, S. (1998)、「連結支配集合の近似アルゴリズム」(PDF)、Algorithmica、20 (4): 374–387、doi : 10.1007/PL00009201、hdl : 1903/830、S2CID 1249122 。
ヘインズ、テレサ・W.、ヘデトニエミ、スティーブン、スレーター、ピーター（1998a）、『グラフにおける支配の基礎』、マルセル・デッカー、ISBN 0-8247-0033-3OCLC 37903553 。
ヘインズ、テレサ・W.、ヘデトニエミ、スティーブン、スレーター、ピーター（1998b）、『グラフにおける支配：高度なトピック』、マルセル・デッカー、ISBN 0-8247-0034-1OCLC 38201061 。
West, Douglas B. (2001), 『グラフ理論入門』（第2 版）、Pearson Education。

[FOOTNOTEGareyJohnson1979-1] ゲイリー＆ジョンソン（1979）。

[FOOTNOTEHedetniemiLaskar1990-2] ヘデトニエミとラスカー (1990)。

[FOOTNOTEKann1992108–109-3] 1 2 Kann (1992)、108 ～ 109 ページ。

[FOOTNOTEEscoffierPaschos2006-4] エスコフィエとパスチョス (2006)。

[FOOTNOTERazSafra1997-5] Raz & Safra (1997)。

[FOOTNOTEParekh1991-6] パレク（1991）。

[FOOTNOTEPapadimitriouYannakakis1991-7] パパディミトリウとヤナカキス (1991)。

[FOOTNOTECrescenziKannHalldórssonKarpinski2000-8] クレシェンツィら（2000）。

[FOOTNOTETakamizawaNishizekiSaito1982-9] 高見沢、西関、斉藤 (1982)。

[FOOTNOTEFominGrandoniPyatkinStepanov2008-10] Fomin et al. (2008)。

[FOOTNOTEAlberFellowsNiedermeier2004-11] アルバー、フェローズ、ニーダーマイヤー (2004)。

[FOOTNOTEFominThilikos2006-12] Fomin & Thilikos (2006)。

[FOOTNOTETelleVillanger2012-13] テルとヴィランジェ (2012)。

[FOOTNOTEDehneFellowsFernauPrieto2006-14] Dehne et al. (2006)。

[FOOTNOTEAllanLaskar1978-15] アラン＆ラスカー（1978）。

[FOOTNOTEAharoniBergerZiv2007-16] 1 2アハロニ、ベルガー、ジヴ (2007)。

[FOOTNOTEWest2001Section_3.1-17] West (2001)、第 3.1 節。

[FOOTNOTEKlasingLaforest2004-18] クラーシングとラフォレスト (2004)。

[FOOTNOTEFörster2013-19] フォルスター (2013)。

[FOOTNOTEHaynesHedetniemiSlater1998-20] ヘインズ、ヘデトニエミ、スレーター (1998)。

[FOOTNOTEMeshulam2003-21] メシュラム (2003)。

[FOOTNOTEBangeBarkauskasSlater1988-22] バンゲ、バルカウスカス、スレーター (1988)。

[FOOTNOTEBrandstädtLeitertRautenbach2012-23] ブランドシュテット、ライタート、ラウテンバッハ (2012)。

[FOOTNOTECockayneDreyerHedetniemiHedetniemi2004-24] Cockayne et al. (2004)。

[FOOTNOTESampathkumar1989-25] サンパスクマール (1989)。

[FOOTNOTEDettlaffLemańskaToppZiemann2020-26] Dettlaff et al. (2020)。

[FOOTNOTEHaynesSlater1998-27] ヘインズ＆スレーター（1998）。

[FOOTNOTEDomkeHattinghHedetniemiLaskar1999-28] ドムケら（1999）。

[FOOTNOTEMerouaneChellali2015-29] メルアン＆チェラリ (2015)。

[FOOTNOTEMahadevanAvadayappanJosephSubramanian2012-30] Mahadevan et al. (2012)。

[FOOTNOTEHaasWexler2004-31] ハース＆ウェクスラー（2004）。

[FOOTNOTEKangShan2020-32] カンとシャン (2020)。

[FOOTNOTECabahug_Jr.EballeFernandez2025-33] カバハグジュニア、エバージェ&フェルナンデス (2025)。

[

[ 2 ]

[

[

[

[ 6 ]

[ 7 ]

[

[

[ 10 ]

[ 11 ]

[

[

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[

[

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

25

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]