부분 k-트리

Partial k-tree

그래프 이론에서 부분 k-트리(partial k-tree)는 그래프의 한 유형으로, k-트리(k-tree)의 서브그래프로 정의되거나 최대 k의 트리 너비가 있는 그래프로 정의된다.그래프의 많은 NP-하드 조합 문제는 k의 경계 값에 대해 부분 k-tree로 제한된 경우 다항식 시간에 해결할 수 있다.

그래프 마이너

부분 3-트리에 대해 금지된 미성년자

고정 상수 k의 경우 부분 k-tree는 그래프 미성년자의 작동에 따라 닫히고, 따라서 Robertson–에 의해 닫힌다.시모어 정리, 이 가문은 금지된 미성년자의 유한 집합의 관점에서 특징지어질 수 있다.부분 1트리는 정확히 숲이고, 그 단 하나의 금지된 부류는 삼각형이다.부분 2-tree의 경우 금지된 단일 부차는 4개의 꼭지점에 있는 완전한 그래프다.그러나 금지된 미성년자의 수는 더 큰 k 값을 얻기 위해 증가한다.부분 3-트리의 경우 4개의 금지된 미성년자가 있다: 5개의 정점에 대한 완전한 그래프, 6개의 정점을 가진 8개의 정점 그래프, 8개의 정점을 가진 바그너 그래프, 그리고 10개의 정점을 가진 오각형 프리즘.[1]

동적 프로그래밍

임의 그래프에 대해 NP-완전한 많은 알고리즘 문제는 동적 프로그래밍을 통해 부분 k-tree에 대해 효율적으로 해결할 수 있으며, 이러한 그래프의 트리 분해를 사용할 수 있다.[2]

관련 그래프 패밀리

그래프 패밀리가 트리 너비를 경계한 경우 부분 k-tree의 하위 패밀리로, 여기서 k는 트리 너비에 대한 경계값이다.이 속성을 가진 그래프 제품군에는 선인장 그래프, 사이비 포리스트, 직렬-병렬 그래프, 외부 평면 그래프, 할린 그래프 및 아폴로니아 네트워크가 포함된다.[1]예를 들어, 직렬-병렬 그래프는 부분 2-tree의 하위 패밀리로, 보다 강력한 그래프는 각각의 쌍방향 구성요소가 직렬-병렬인 경우에만 부분 2-tree이다.

구조화 프로그램의 편성에서 발생하는 제어 흐름 그래프에도 테두리 트리 너비가 있어 레지스터 할당과 같은 특정 작업을 효율적으로 수행할 수 있다.[3]

메모들

  1. ^ a b 보들렌더(1998년).
  2. ^ Arnborg & Proskurowski (1989년), Bern, Lauler & Wong (1987년), Bodlaender (1988년)
  3. ^ 토럽(1998년).

참조

  • Arnborg, S.; Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial k-trees", Discrete Applied Mathematics, 23 (1): 11–24, doi:10.1016/0166-218X(89)90031-0.
  • Bern, M. W.; Lawler, E. L.; Wong, A. L. (1987), "Linear-time computation of optimal subgraphs of decomposable graphs", Journal of Algorithms, 8 (2): 216–235, doi:10.1016/0196-6774(87)90039-3.
  • Bodlaender, Hans L. (1988), "Dynamic programming on graphs with bounded treewidth", Proc. 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 317, Springer-Verlag, pp. 105–118, doi:10.1007/3-540-19488-6_110, ISBN 978-3-540-19488-0.
  • Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4, hdl:1874/18312.
  • Thorup, Mikkel (1998), "All structured programs have small tree width and good register allocation", Information and Computation, 142 (2): 159–181, doi:10.1006/inco.1997.2697.