예열연장
Precoloring extension그래프 이론에서, 사전 배색 확장은 특정한 색상 집합을 가진 그래프의 정점 부분 집합의 그래프 색상을 인접한 정점 두 개에 동일한 색상을 할당하지 않는 전체 그래프의 색상으로 확장하는 문제다.
복잡성
사전 배색 확장자는 특별한 경우로서 일반적인 그래프 색칠 문제를 가지고 있는데, 이 경우 정점의 초기 색상 부분 집합은 비어 있으므로 NP-완전이다.그러나 일반적인 그래프 컬러링 문제가 더 쉬운 일부 다른 등급의 그래프에 대해서도 NP 완료가 된다.예를 들어, 이것은 부분적으로 채워진 라틴 사각형을 완성하는 문제에 해당하는 룩의 그래프에서 NP-완전이다.[1]
경계가 있는 트리 너비의 그래프의 경우 다항 시간 내에 문제를 해결할 수 있지만 다항식의 지수는 트리 너비에 따라 달라진다.[2][3]색상 수와 트리 너비가 모두 경계인 확장 인스턴스를 사전 추출하기 위해 선형 시간 내에 해결할 수 있다.[2]
관련 문제
사전 배색 확장은 정점이 없는 그래프를 색칠하는 문제인 목록 색상의 특별한 경우로 볼 수 있지만, 각 정점에는 사용 가능한 색의 목록이 지정되어 있다.사전 지정 확장 문제를 목록 색상 문제로 변환하려면 사전 지정 확장 문제에서 각 미지정 정점을 초기 색상 인접 네트워크에서 아직 사용되지 않은 색 목록으로 지정한 다음 그래프에서 색상이 지정된 정점을 제거하십시오.
스도쿠 퍼즐은 스도쿠 그래프에 있는 사전 추출 확장 문제의 예로서 수학적으로 모델링될 수 있다.[4][5]
참조
- ^ Colbourn, Charles J. (1984), "The complexity of completing partial Latin squares", Discrete Applied Mathematics, 8 (1): 25–30, doi:10.1016/0166-218X(84)90075-1, MR 0739595.
- ^ a b Jansen, Klaus; Scheffler, Petra (1997), "Generalized coloring for tree-like graphs", Discrete Applied Mathematics, 75 (2): 135–155, doi:10.1016/S0166-218X(96)00085-6, MR 1451958
- ^ Fellows, Michael R.; Fomin, Fedor V.; Lokshtanov, Daniel; Rosamond, Frances; Saurabh, Saket; Szeider, Stefan; Thomassen, Carsten (2011), "On the complexity of some colorful problems parameterized by treewidth", Information and Computation, 209 (2): 143–153, doi:10.1016/j.ic.2010.11.026, MR 2790022
- ^ Herzberg, Agnes M.; Murty, M. Ram (2007), "Sudoku squares and chromatic polynomials", Notices of the American Mathematical Society, 54 (6): 708–717, MR 2327972
- ^ Rosenhouse, Jason; Taalman, Laura (2011), Taking Sudoku Seriously: The math behind the world's most popular pencil puzzle, Oxford University Press, p. 130
외부 링크
- 단니엘 마르크스 예초연장에 관한 문헌 목록
