지배집합

그래프 이론에서, 그래프 G = (V, E)에 대한 지배 집합은 D에 없는 모든 정점이 D의 적어도 하나의 부재에 인접하도록 정점 V의 부분 집합이다.도미네이션 번호 θ(G)는 G에 대한 가장 작은 도미네이션 세트 내의 정점 수입니다.

지배적인 집합 문제는 주어진 그래프 G와 입력 K에 대해 δ(G) δ K 여부를 테스트하는 것과 관련이 있다. 이것은 계산 복잡도 ^[1]이론의 고전적인 NP-완전 결정 문제이다.따라서 효율적인 근사 알고리즘은 물론 특정 그래프 클래스에 대한 효율적이고 정확한 알고리즘도 있지만 모든 그래프에 대해 가장 작은 지배 집합을 찾는 효율적인 알고리즘은 없을 수 있다.

역사

지배 문제는 1950년대부터 연구되었지만, 1970년대 중반에는 지배에 대한 연구 비율이 크게 증가했다.1972년 Richard Karp는 세트 커버 문제가 NP-완전하다는 것을 증명했습니다.이것은 두 문제 사이에 설정할 수 있는 간단한 정점이 있고 비분리 교차로 분사에 가장자리가 있기 때문에 지배적인 집합 문제에 즉각적인 영향을 미쳤다.이것에 의해,^[2] 지배적인 집합 문제도 NP-완전인 것이 증명되었습니다.

지배적인 세트는 몇 가지 영역에서 실제로 관심이 있습니다.무선 네트워크에서는 애드혹모바일 네트워크 내에서 효율적인 루트를 찾기 위해 지배 세트를 사용합니다.또한 문서 요약 및 전기 그리드의 보안 시스템 설계에도 사용되었습니다.

지배적 및 독립적 집합

지배집합은 독립집합과 밀접하게 관련되어 있다.독립집합은 그것이 최대 독립집합인 경우에만 지배집합이다.그래프 내의 어떤 최대 독립집합도 필연적으로 최소 지배집합이다.

독립집단에 의한 지배

지배집합은 독립집합일 수도 있고 아닐 수도 있다.예를 들어 (a) 및 (b)는 독립된 지배집합을 나타내고 (c)는 독립된 지배집합이 아닌 지배집합을 나타낸다.

그래프 G의 독립 지배 번호 i(G)는 독립 집합인 최소 지배 집합의 크기이다.마찬가지로, 이것은 가장 작은 최대 독립 집합의 크기입니다.i(G)의 최소값은 더 적은 요소(독립 집합만 고려됨)보다 우선하므로 모든 그래프 G에 대해 θ(G) i i(G)이다.

부등식은 엄격할 수 있다 - G에 대한 그래프 G는 θ(G) < i(G)이다.예를 들어, ${\displaystyle {}_{}}$는 $정점{\displaystyle {}_{}}$ x${\displaystyle {1\mathrm{}}_{}}$, ${\displaystyle \dots ,{}_{}{x}_{}}$ ${\displaystyle p,}$ ${\displaystyle a,}$ ${\displaystyle {}_{}}$, ${\displaystyle {y\mathrm{}}_{}}$1,${\displaystyle \dots ,}$ ${\displaystyle y_{}}$q {$style x_{1}, x_{p}, a, b, y_{1},$ \$ldots, y_{q$로 이루어진 이중 별 그래프입니다.여기서 p, q > 1은 1입니다.G의 가장자리는 다음과 같이 정의됩니다.각_i x는 a에 인접하고, a는 b에 인접하며, b는 y에_j 인접합니다.그러면 {a, b}는 가장 작은 지배 집합이므로 θ(G) = 2이다.p qq일 ${\displaystyle {}_{}}$ { x${\displaystyle {}_{}}$, ${\displaystyle \dots ,{}_{}{x}_{}}$ ${\displaystyle p}$, b$$}({$displaystyle$\{$x_{1},\ldots,x_{p},$b$$$\backslash \}){\displaystyle }$이므로 i(G) = p + 1은 독립성이 있는 최소 지배 집합입니다(최대 독립 집합).

θ(G) = i(G)인 그래프 패밀리가 있다. 즉, 모든 최소 최대 독립 집합이 최소 지배 집합이다.예를 들어, G가 발톱이 없는 ^[3]그래프인 경우 θ(G) = i(G)입니다.

그래프 G는 G의 모든 유도 부분 그래프 H에서 θ(H) = i(H)이면 지배-완벽 그래프라고 불린다. 발톱이 없는 그래프의 유도 부분 그래프는 발톱이 없기 때문에, 모든 발톱이 없는 그래프도 지배-완벽한 ^[4]그래프이다.

어느 그래프 G에서도 선 그래프 L(G)은 손톱이 없기 때문에 L(G)에서의 최소 최대 독립 집합도 L(G)에서의 최소 지배 집합이다.L(G)의 독립집합은 G의 매칭에 대응하고, L(G)의 지배집합은 G의 에지 지배집합에 대응한다.따라서 최소 최대 일치의 크기는 최소 에지 지배 세트와 동일합니다.

독립 집합의 지배

그래프 G의 독립 지배수 iδ(G)는 ^[5]A를 지배하는 최소 집합의 모든 독립 집합 A에 대한 최대값이다.정점의 서브셋을 지배하려면 모든 정점을 지배할 때보다 더 적은 정점이 필요할 수 있으므로 모든 그래프 G에 대해 iγ(G) ≤(G) ≤(G)가 필요합니다.

부등식은 엄격할 수 있다. i g(G) < ((G) 그래프 G가 있다.예를 들어, 어떤 정수 n의 경우, G는 꼭짓점이 n-by-n 보드의 행과 열이며, 이러한 두 꼭짓점이 교차하는 경우에만 연결되는 그래프라고 가정합니다.유일한 독립 집합은 행 또는 열로만 구성된 집합이며, 각 집합은 하나의 정점에 의해 지배될 수 있으므로, iθ(G) = 1이다. 그러나 모든 정점을 지배하기 위해서는 적어도 하나의 행과 하나의 열이 필요하다. 따라서 θ(G) = 2. 또한, 임의로 θ(G) / θ(G) 사이의 비율이 클 수 있다.예를 들어, G의 정점이 n-by-n 보드의 모든 제곱 부분 집합인 경우에도 iθ(G) = 1이지만 θ(G) = ^[5]n이다.

그래프 G의 bi-dependent domination number iii(G)는 A를 지배하는 최소 독립 집합의 모든 독립 집합 A에 대한 최대값이다.그래프 G에는 다음 관계가 있습니다.

$(\displaystyle\begin{aligned}i(G)&\geqi\gamma(G)&\geqi(G)&\geqi\gamma(G)&\end{aligned})$

알고리즘과 계산의 복잡성

세트 커버 문제는 잘 알려진 NP-하드 문제이며 세트 커버의 결정 버전은 Karp의 21개의 NP-완전 문제 중 하나였습니다.최소 지배 세트 문제와 세트 커버 ^[6]문제 사이에는 한 쌍의 다항식 시간 L 감소가 존재합니다.이러한 삭감(아래를 참조)에 의해, 지배적인 최소의 세트 문제에 대한 효율적인 알고리즘이 세트 커버 문제에 대한 효율적인 알고리즘을 제공할 수 있는 것을 알 수 있습니다.또, 그 반대의 경우도 마찬가지입니다.또한, 감소는 근사 비율을 보존한다. 모든 α에 대해 최소 지배 집합에 대한 다항식 시간 α 근사 알고리즘은 집합 커버 문제에 대한 다항식 시간 α 근사 알고리즘을 제공할 것이며, 그 반대도 마찬가지이다.두 문제 모두 실제로는 Log-APX-complete입니다.^[7]

집합 피복의 근사성도 잘 이해된다. 단순한 탐욕 알고리즘을 사용하여 로그 근사 계수를 찾을 수 있으며, 하위 대수 근사 계수를 찾는 것은 NP-hard이다.보다 구체적으로, 탐욕 알고리즘은 최소 지배 집합의 계수 1 + 로그 V 근사치를 제공하며, 어떤 다항식 시간 알고리즘도 P = ^[8]NP가 아닌 한 일부 c > 0에 대해 c 로그 V보다 더 나은 근사 계수를 얻을 수 없다.

L-감소

다음 두 가지 감소는 최소 지배적인 세트 문제와 세트 커버 문제가 L 감소에서 동등함을 나타냅니다. 한 가지 문제가 주어진 경우 다른 문제와 ^[6]동등한 인스턴스를 구성할 수 있습니다.

지배적인 세트에서 세트 커버로

V = {1, 2, ..., n}인 그래프 G = (V, E)가 주어졌을 때, 집합 덮개 인스턴스(U, S₂)를 다음과 같이 구성합니다. 우주 U는 V이고, 부분 집합의 패밀리는 S₁ = {S, S_n, ..., S}이며, S는_v V의 정점과 인접한 모든 정점으로 구성됩니다.

D가 G의 지배적 집합이라면, C = {S_v : v d D}는 C = D일 때 집합 커버 문제의 실현 가능한 해이다. 반대로, C = {S_v : v d D}가 집합 커버 문제의 실현 가능한 해라면, D는 D = C일 때 집합 커버 문제의 지배적 집합이다.

따라서 G에 대한 최소 지배 세트의 크기는 (U, S)에 대한 최소 설정 커버의 크기와 같다.또한 지배적인 세트를 같은 크기의 세트 커버에 매핑하는 간단한 알고리즘이 있다.특히 세트 피복을 위한 효율적인 α 근사 알고리즘은 최소 지배 세트를 위한 효율적인 α 근사 알고리즘을 제공한다.

예를 들어 오른쪽에 표시된 그래프 G에서 우주 U = {1, 2, ..., 6}과(와) 하위 집합₁ S = {1, 2, 5}, S₂₃ = {1, 2, 3, 6, S₄ = {2, 3, 4, 4, S₅ = {3, 5, 6}을(를) 사용하여 집합 커버 인스턴스를 구성합니다.이 예에서 D = {3, 5}은 G에 대한 지배적 집합이다 – 이것은 세트 커버 C = {S₃, S₅}에 해당한다. 예를 들어, 정점 4 µ V는 정점 3 µ D에 의해 지배되고 요소 4 µ U는 세트₃ S µ C에 포함된다.

세트 커버에서 지배 세트까지

(S, U)가 우주 U와 부분 집합 S = {S_i : i δ I}에 대한 집합 덮개 문제의 인스턴스라고 가정하자. 우리는 U와 지수 집합 I가 분리된 것으로 가정한다.그래프 G = (V, E)를 다음과 같이 구성합니다. 정점 집합은 V = I u U이고, 각 쌍 i, j i I 사이에 가장자리 {i, j} e E가 있으며, 각 i i I 및 u s_i S에 대한 가장자리 {i, u}도 있습니다.즉, G는 분할 그래프입니다.나는 파벌이고 U는 독립된 집합이다.

C = {S_i : i d D}가 어떤 부분집합 D , I에 대한 집합 커버 문제의 실현 가능한 해라면, D는 G에 대한 지배적인 집합이며, D = C : 첫째, 각 u u U에 대해 u s_i S가 있고, 따라서 시공에 의해 u와 인접한 G에 지배되는 i d D가 있다.둘째, D는 비어 있지 않아야 하므로 각 i i I는 D의 정점에 인접한다.

반대로, D를 G의 지배적인 집합으로 하자.다음으로 X d D 및 X i I: 단순히 각 u d D by U를 u의 인접 i i I로 치환하도록 다른 지배집합 X를 구축할 수 있다.C = {S_i : i x X}는 C = X d D인 집합 덮개 문제의 실현 가능한 해이다.

오른쪽 그림은 U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S₁ = {a, b, c₃}, S₂ = {b, c, d} 및 S₄ = {c, d, e}에 대한 구성을 보여줍니다.

이 예에서 C = {S₁, S₄}는 세트 커버이며, 이는 지배적인 세트 D = {1, 4}에 해당합니다.

D = {a, 3, 4}는 그래프 G의 또 다른 지배 집합입니다. D가 주어지면 D보다 크지 않고 I의 부분 집합인 X = {1, 3, 4}을(를) 구성할 수 있습니다.지배 세트 X는 세트 커버 C = {S₁, S₃, S₄}에 해당합니다.

특수한 경우

그래프가 최대도 δ인 경우, 탐욕 근사 알고리즘은 최소 지배 세트의 O(log δ) 근사치를 구한다.또한 d는 탐욕 근사를 사용하여 얻은 지배집합의 카디널리티이며, 다음_g 관계 $홀드{\displaystyle {}_{}}$ ${\displaystyle d_{}}$ g${\displaystyle {}_{}n}$N +${\displaystyle 1\sqrt{\mathrm{}}}$ - 2${\displaystyle \sqrt{M}}$ +$$ \ $displaystyle d$_ { $g$} \$leq$N + 1 - { \ $sqrt${$2M$+ $1$} 입니다$.$여기서 N은 주어진 무방향 ^[9]그래프의 에지 수입니다.고정 δ의 경우 이는 APX 멤버십의 지배적인 세트로 간주됩니다.실제로 APX 완전입니다.^[10]

이 문제는 단위 디스크 그래프 및 평면 ^[11]그래프와 같은 특수한 경우에 대해 다항식 시간 근사 체계(PTAS)를 허용한다.최소 지배 세트는 직렬-병렬 ^[12]그래프에서 선형 시간으로 찾을 수 있습니다.

정확한 알고리즘

모든 정점 서브셋을 검사함으로써 시간 O(2nⁿ)에서 n-vertex 그래프의 최소 지배 세트를 찾을 수 있다.Fomin, Grandoni & Kratch(2009)는 시간 O(1.5137ⁿ)와 지수 공간, 시간 O(1.5264ⁿ)와 다항식 공간에서 최소 지배 집합을 찾는 방법을 보여준다.O(1.5048ⁿ) 시간을 사용한 보다 빠른 알고리즘은 van Roij, Nederlof 및 van Dijk(2009)에 의해 발견되었으며, 이들은 또한 이 시간에 최소 지배 세트의 수를 계산할 수 있음을 보여준다.최소 지배 세트의 수는 최대 1.7159개이며ⁿ 이러한 모든 세트를 시간 O(1.7159)^[13]에ⁿ 나열할 수 있습니다.

파라미터화된복잡도

크기 k의 지배적인 집합을 찾는 것은 매개 변수화된 복잡성 이론에서 중심적인 역할을 한다.이것은 클래스 W[2]에 대해 가장 잘 알려진 문제이며, 다른 문제의 난해성을 나타내기 위해 많은 감소로 사용됩니다.특히, W 계층이 FPT=W[2]로 붕괴하지 않는 한 함수 f에 대해 실행 시간 f(k^O(1))n을 갖는 알고리즘이 존재하지 않는다는 점에서 이 문제는 고정 매개 변수를 추적할 수 없다.

한편 입력 그래프가 평면일 경우 문제는 NP-hard로 유지되지만 고정 파라미터 알고리즘이 알려져 있습니다.실제로 이 문제는 k ^[14]단위의 선형 크기의 커널을 가지며,^[15] 커널의 분기 분해에 동적 프로그래밍을 적용함으로써 δk 단위의 기하급수적인 실행 시간을 얻을 수 있다.보다 일반적으로 지배적인 집합 문제와 문제의 많은 변형은 지배적인 집합의 크기와 가장 작은 금지된 완전 이분 하위 그래프의 크기에 의해 매개 변수화되었을 때 고정 매개 변수를 추적할 수 있다. 즉, 문제는 평면 g를 포함하는 매우 일반적인 종류의 희박한 그래프인 쌍곡선 없는 그래프의 FPT이다.라프.^[16]

지배적인 집합인 비블로커에 대한 보완 세트는 모든 ^[17]그래프에서 고정 파라미터 알고리즘으로 찾을 수 있습니다.

변종

지배 세트의 중요한 서브 클래스는 연결된 지배 세트의 클래스입니다.S가 연결된 지배집합일 경우, S가 트리의 잎이 아닌 정점의 집합을 형성하는 G의 스패닝 트리를 형성할 수 있으며, 반대로 T가 3개 이상의 정점이 있는 그래프 내의 임의의 스패닝 트리일 경우 T의 잎이 아닌 정점은 연결된 지배집합을 형성한다.따라서 연결된 최소 지배 세트를 찾는 것은 가능한 최대 리프 수를 가진 스패닝 트리를 찾는 것과 같습니다.

전체 지배 집합은 그래프 내의 모든 정점(지배 집합 자체의 정점 포함)이 지배 ^[18]집합 내에 인접 관계를 가지도록 하는 정점 집합입니다.상기 (c)는 접속된 지배집합과 토탈 지배집합을 나타내며, 그림 (a) 및 (b)의 예는 어느 쪽도 아니다.

k-튜플 지배집합은 그래프 내의 각 정점이 세트 내에 적어도 k개의 네이버를 가지도록 하는 정점의 집합이다.최소 k-튜플 지배 세트의 (1 + log n)-근사를 다항식 ^[19]시간으로 구할 수 있다.마찬가지로 k-지배 집합은 집합 내에 없는 각 정점이 집합 내에 최소 k개의 인접점을 가지도록 하는 정점 집합입니다.모든 그래프는 k-지배적 집합을 허용하지만, 최소 도수가 k - 1인 그래프만 k-태플 지배적 집합을 허용한다.단, 그래프에 k-튜플 지배집합이 허용되어도 최소 k-튜플 지배집합은 동일 ^[20]그래프에 대한 최소 k-도미네이션 집합의 약 k배이며, 최소 k-도미네이션 집합의 An(1.7+log δ)-근사치도 다항식 시간으로 구할 수 있다.

별 지배 집합은 V의 모든 정점 v에 대해 V의 별(v에 인접한 가장자리 집합)이 D의 일부 정점의 별과 교차하도록 V의 부분 집합이다.확실히 G에 고립된 정점이 있으면 별 지배적인 집합이 없습니다(분리된 정점의 별은 비어있기 때문입니다).G에 고립된 정점이 없는 경우 모든 지배 집합은 별 지배 집합이며 그 반대도 마찬가지입니다.별 지배와 통상 지배의 차이는 그들의 부분적 변형을 ^[21]고려할 때 더 실질적이다.

돔 파티션은 정점들을 분리된 지배 집합으로 나누는 파티션입니다.돔 번호는 돔 파티션의 최대 크기입니다.

영속 지배집합은 지배집합 D의 정점 v가 선택되고 수정된 D도 지배집합이 되도록 이웃집합 u(u는 D에 없음)로 치환되는 동적 지배집합이며, 이 과정은 정점 v의 무한계열에 걸쳐 반복할 수 있다.

「 」를 참조해 주세요.

• Vizing의 추측 - 그래프의 데카르트 곱의 지배 번호와 요인의 지배 수를 관련짓습니다.
• 커버 설정 문제
• 속박 번호

메모들

레퍼런스

• 를 클릭합니다Alber, Jochen; Fellows, Michael R; Niedermeier, Rolf (2004), "Polynomial-time data reduction for dominating set", Journal of the ACM, 51 (3): 363–384, arXiv:cs/0207066, doi:10.1145/990308.990309, S2CID 488501.
• 를 클릭합니다Allan, Robert B.; Laskar, Renu (1978), "On domination and independent domination numbers of a graph", Discrete Mathematics, 23 (2): 73–76, doi:10.1016/0012-365X(78)90105-X.
• 를 클릭합니다Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum dominating set", A Compendium of NP Optimization Problems.
• Dehne, 프랭크, 멤버들, 마이클 Fernau, 헤닝;프리에토, 엘레나, Rosamond, 프랜시스(2006년),"Nonblocker:최소 배짱에 Parameterized algorithmics 세트"(PDF), SOFSEM 2006년:이론 기술 개발 현황에 32회의 컴퓨터 과학, Merin, 체코, 1월 21일부터 27일, 2006년, 회보, 강의 노트 컴퓨터 과학으로, vo의 연습하다L.3831, 스프링거,를 대신하여 서명함. 237–245, doi:10.1007/11611257_21.
• Escoffier, Bruno; Paschos, Vangelis Th. (2006), "Completeness in approximation classes beyond APX", Theoretical Computer Science, 359 (1–3): 369–377, doi:10.1016/j.tcs.2006.05.023
• 를 클릭합니다Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", 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), "A measure & conquer approach for the analysis of exact algorithms", 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), "Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications", ACM Transactions on Algorithms, 5 (1): 9:1–17, doi:10.1145/1435375.1435384, S2CID 2489447.
• 를 클릭합니다Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), "Dominating sets in planar graphs: branch-width and exponential speed-up", SIAM Journal on Computing, 36 (2): 281, doi:10.1137/S0097539702419649, S2CID 5232238.
• 를 클릭합니다Förster, Klaus-Tycho. (2013), "Approximating Fault-Tolerant Domination in General Graphs", Proc. of the Tenth Workshop on Analytic Algorithmics and Combinatorics ANALCO, SIAM, pp. 25–32, doi:10.1137/1.9781611973037.4, ISBN 978-1-61197-254-2.
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, 페이지 190, 문제 GT2.
• 를 클릭합니다Hedetniemi, S. T.; Laskar, R. C. (1990), "Bibliography on domination in graphs and some basic definitions of domination parameters", Discrete Mathematics, 86 (1–3): 257–277, doi:10.1016/0012-365X(90)90365-O.
• Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF). PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm{{citation}}: CS1 maint : postscript (링크).
• 를 클릭합니다Klasing, Ralf; Laforest, Christian (2004), "Hardness results and approximation algorithms of k-tuple domination in graphs", Information Processing Letters, 89 (2): 75–83, doi:10.1016/j.ipl.2003.10.004.
• Papadimitriou, Christos H.; Yannakakis, Mihailis (1991), "Optimization, Approximation, and Complexity Classes", Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016/0022-0000(91)90023-X
• Parekh, Abhay K. (1991), "Analysis of a greedy heuristic for finding small dominating sets in graphs", Information Processing Letters, 39 (5): 237–240, doi:10.1016/0020-0190(91)90021-9
• 를 클릭합니다Raz, R.; Safra, S. (1997), "A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP", Proc. 29th Annual ACM Symposium on Theory of Computing, ACM, pp. 475–484, doi:10.1145/258533.258641, ISBN 0-89791-888-6, S2CID 15457604.
• 를 클릭합니다Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs", Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328, S2CID 16082154.
• Telle, 얀 아르네;Villanger, Yngve(2012년),"biclique-free 그래프에 지배를 위해 FPT 알고리즘", 엡스타인은 레아에, Ferragina, 파올로(eds.), 알고리즘 – ESA2012년:20회 유럽 심포지엄, 류블랴나, 슬로베니아, 9월 10–12, 2012년, 회보, 강의 노트 컴퓨터 과학으로, 7501 vol., 스프링거,를 대신하여 서명함. 802–812,. doi:10.1007/978-3-642-33090-2_69.
• 를 클릭합니다van Rooij, J. M. M.; Nederlof, J.; van Dijk, T. C. (2009), "Inclusion/Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets", Proc. 17th Annual European Symposium on Algorithms, ESA 2009, Lecture Notes in Computer Science, vol. 5757, Springer, pp. 554–565, doi:10.1007/978-3-642-04128-0_50, ISBN 978-3-642-04127-3.

추가 정보

• 를 클릭합니다Grandoni, F. (2006), "A note on the complexity of minimum dominating set", 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), "Approximation algorithms for connected dominating sets" (PDF), Algorithmica, 20 (4): 374–387, doi:10.1007/PL00009201, hdl:1903/830, S2CID 1249122.
• 를 클릭합니다Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, Marcel Dekker, ISBN 0-8247-0033-3, OCLC 37903553.
• 를 클릭합니다Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998b), Domination in Graphs: Advanced Topics, Marcel Dekker, ISBN 0-8247-0034-1, OCLC 38201061.
• 를 클릭합니다West, Douglas B. (2001), Introduction to Graph Theory (2 ed.), Pearson Education.