연결된 지배 세트

Connected dominating set

그래프 이론에서, 연결된 지배적 집합과 최대 잎사귀 확장 트리는 비방향 그래프에 정의된 두 개의 밀접하게 연관된 구조물이다.

정의들

그래프 G의 연결된 지배적인 집합은 두 가지 속성을 가진 정점의 집합 D이다.

  1. D의 어떤 노드는 전적으로 D 내에 머무르는 경로를 통해 D의 다른 노드에 도달할 수 있다.즉, D는 G의 연결된 서브그래프를 유도한다.
  2. G의 모든 꼭지점은 D에 속하거나 D의 꼭지점에 인접한다.즉, D는 지배적인 G의 집합이다.

그래프 G의 최소 연결 지배 집합은 G의 모든 연결된 지배 집합 중에서 가능한 가장 작은 카디널리티를 가진 연결된 지배 집합이다.G의 연결된 지배 번호는 최소로 연결된 지배 집합의 정점 수입니다.[1]

그래프 G의 스패닝 트리 T는 최소 두 개의 잎을 가지고 있는데, 정점에는 T 사건의 한쪽 가장자리만 있다.최대 잎사귀 스패닝 트리는 G의 모든 스패닝 트리 중에서 가능한 가장 많은 수의 잎을 가진 스패닝 트리다.G의 최대 잎 수는 최대 잎 스패닝 트리에 있는 잎의 수입니다.[2]

상보성

만약 d가 n > 2의 n-vertex 그래프 G의 연결된 지배수이고 l가 그것의 최대 잎수라면, d, l, n 세 수량은 단순한 방정식을 따른다.

[3]

D가 연결된 지배하는 집합인 경우, G에는 신장 트리가 존재하며, 잎에는 D: D에 있지 않은 나머지 각 정점 v를 D에 있지 않은 이웃에 연결하는 가장자리와 함께 D:에 없는 서브그래프의 신장 트리를 형성한다.이것은 l ≥ n - d를 보여준다.

다른 방향에서 T가 G의 어떤 스패닝 트리인 경우, 잎이 아닌 T의 정점이 G의 연결된 지배적인 집합을 형성한다.이것은 n - l ≥ d. 이 두 불평등을 합치면 n = d + l의 평등이 입증된다는 것을 보여준다.

따라서 어떤 그래프에서든 연결된 지배 번호와 최대 리프 수의 합은 정점의 총 수와 같다.계산적으로, 이것은 연결된 지배 수를 결정하는 것이 최대 잎 수를 찾는 것과 마찬가지로 어렵다는 것을 암시한다.

알고리즘

지정된 임계값보다 작은 크기의 연결된 지배 집합이 있는지 또는 최소한 지정된 수의 잎을 가진 스패닝 트리가 있는지 여부를 동등하게 테스트하는 것은 NP-완전이다.따라서, 최소 연계된 지배적 세트 문제, 그리고 다항식 시간에는 최대 잎사귀 확장 문제를 해결할 수 없다고 생각된다.

근사 알고리즘 측면에서 볼 때, 연결된 지배와 트리에 걸쳐 있는 최대 잎은 같지 않다. 주어진 근사 비율 내에서 1 대 1의 근사치는 다른 대 동일한 비율에 근사치하는 것과 같지 않다.2 ln Δ + O(1)의 인수를 달성하는 최소 연결 지배 집합에 대한 근사치가 있으며, 여기서 Δ는 G에서 정점의 최대 수준이다.[4]최대 리프 스패닝 트리 문제는 MAX-SNP 하드로, 다항식 시간 근사 체계가 없을 가능성이 있음을 암시한다.[5]단, 다항식 시간에서 2의 요인 내에 근사치를 구할 수 있다.[6]

n-vertex 그래프에서n 시간 O(1.9) 내에 두 문제를 모두 해결할 수 있다.[7]최대 잎문제는 고정 매개변수 추적가능하며, 이는 잎 수는 시간 지수적으로 해결할 수 있지만 입력 그래프 크기에서는 다항식만 가능하다는 것을 의미한다.이러한 알고리즘의 클램 값(직관적으로, 합리적인 시간 내에 문제를 해결할 수 있는 다수의 잎)은 문제의 알고리즘이 개선됨에 따라 점차적으로 약 37개로 증가했으며,[8] 적어도 50개는 달성할 수 있어야 한다는 의견이 제시되었다.[9]

최대도 3의 그래프에서, 연결된 지배 집합과 그것의 보완적인 최대 잎 신장 트리 문제는 선형 매트로이드에 대한 매트로이드 패리티 문제의 한 인스턴스로 변환함으로써 다항식 시간에 해결할 수 있다.[10]

적용들

연결된 지배적 집합은 모바일 애드혹 네트워크의 라우팅 계산에 유용하다.이 어플리케이션에서는, 통신의 백본으로서 연결된 작은 지배집합 집합이 이용되고, 이 집합에 있지 않은 노드는 집합에 있는 이웃을 통해서 메시지를 전달함으로써 통신한다.[11]

최대 리프 번호는 고정 매개변수 추적 가능한 알고리즘 개발에 채택되었다. 경계 최대 리프 번호 그래프의 경우 여러 NP-하드 최적화 문제를 다항 시간 내에 해결할 수 있다.[2]

참고 항목

  • 범용 꼭지점, (존재할 때) 크기가 최소로 연결된 지배적인 집합의 크기를 제공하는 꼭지점

참조

  1. ^ Sampathkumar, E.; Walikar, HB (1979), "The connected domination number of a graph", J. Math. Phys. Sci, 13 (6): 607–613.
  2. ^ a b Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Mnich, Matthias; Rosamond, Frances; Saurabh, Saket (2009), "The complexity ecology of parameters: an illustration using bounded max leaf number", Theory of Computing Systems, 45 (4): 822–848, doi:10.1007/s00224-009-9167-9.
  3. ^ Douglas, Robert J. (1992), "NP-completeness and degree restricted spanning trees", Discrete Mathematics, 105 (1–3): 41–47, doi:10.1016/0012-365X(92)90130-8.
  4. ^ Guha, S.; Khuller, S. (1998), "Approximation algorithms for connected dominating sets", Algorithmica, 20 (4): 374–387, doi:10.1007/PL00009201, hdl:1903/830.
  5. ^ Galbiati, G.; Maffioli, F.; Morzenti, A. (1994), "A short note on the approximability of the maximum leaves spanning tree problem", Information Processing Letters, 52 (1): 45–49, doi:10.1016/0020-0190(94)90139-2.
  6. ^ Solis-Oba, Roberto (1998), "2-approximation algorithm for finding a spanning tree with maximum number of leaves", Proc. 6th European Symposium on Algorithms (ESA'98), Lecture Notes in Computer Science, vol. 1461, Springer-Verlag, pp. 441–452, doi:10.1007/3-540-68530-8_37, hdl:11858/00-001M-0000-0014-7BD6-0.
  7. ^ Fernau, Henning; Kneis, Joachim; Kratsch, Dieter; Langer, Alexander; Liedloff, Mathieu; Raible, Daniel; Rossmanith, Peter (2011), "An exact algorithm for the maximum leaf spanning tree problem", Theoretical Computer Science, 412 (45): 6290–6302, doi:10.1016/j.tcs.2011.07.011, MR 2883043.
  8. ^ Binkele-Raible, Daniel; Fernau, Henning (2014), "A parameterized measure-and-conquer analysis for finding a k-leaf spanning tree in an undirected graph", Discrete Mathematics & Theoretical Computer Science, 16 (1): 179–200, MR 3188035.
  9. ^ Fellows, 마이클 R.;McCartin, 캐서린. Rosamond, 프랜시스 A;.Stege, Ulrike(2000년),"Coordinatized 알갱이와 촉매 감소:최대 잎에 관한 개선된 FPT 알고리즘 나무와 다른 문제들에 이르는", FST-TCS 2000년:소프트웨어 기술 이론 컴퓨터 과학의 기초, 강의 노트 Comput에.Sci.,vol. 1974년, 스프링거, 베를린, pp. 240–251, doi:10.1007/3-540-44450-5_19, MR1850108.
  10. ^ Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three", Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), Discrete Mathematics, 72 (1–3): 355–360, doi:10.1016/0012-365X(88)90226-9, MR 0975556
  11. ^ Wu, J.; Li, H. (1999), "On calculating connected dominating set for efficient routing in ad hoc wireless networks", Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, ACM, pp. 7–14, doi:10.1145/313239.313261.