우리는 k를 입력으로 요구하지 않고 그래프의 색수(χ)를 추정하는 Petford-Welsh 색칠 알고리즘의 동적 확장을 제안합니다. 기본 알고리즘은 이징 모델 해밀토니안을 최소화하는 볼츠만 기계와 밀접하게 관련된 모델에 기반합니다. 이 방법은 최소한의 색칠로 시작하여 솔루션 품질에 따라 색상 수를 적응적으로 조정합니다. 우리는 다양한 초기화 전략을 사용하여 DIMACS 벤치마크 수트의 다양한 그래프에 대해 접근 방식을 평가합니다. 결과는 설계된 알고리즘이 거의 최적의 솔루션을 제공할 수 있을 뿐만 아니라 매우 강력하다는 것을 보여줍니다. 우리는 이 접근 방식이 실제 사례에서도 놀라울 정도로 효과적일 수 있음을 입증하지만, 더 어려운 경우에는 보다 적응적이거나 문제에 특화된 전략이 필요할 수 있습니다. 제안된 무작위 알고리즘의 주요 장점은 미래 연구에서 탐색될 수 있는 고유한 병렬성입니다.
Bihani et al. (Thu,)가 이 질문을 연구했습니다.