만약 폭탄을 최소로 사용해야 하는 문제라면, 도시가 0과 2로만 이루어져 있고 K = 1일 때 이 문제는 임의의 격자 그래프에서 minimum dominating set을 찾는 문제가 됩니다. 이 문제는 NP-complete임이 증명되어 있습니다(Clark, Colbourn & Johnson (1990).). 또한 K = ∞인 경우는 NP-hard임이 증명되어 있습니다(Alpert & Roldán (2021).).
2345번 - 지뢰 제거
만약 폭탄을 최소로 사용해야 하는 문제라면, 도시가 0과 2로만 이루어져 있고 K = 1일 때 이 문제는 임의의 격자 그래프에서 minimum dominating set을 찾는 문제가 됩니다. 이 문제는 NP-complete임이 증명되어 있습니다(Clark, Colbourn & Johnson (1990).). 또한 K = ∞인 경우는 NP-hard임이 증명되어 있습니다(Alpert & Roldán (2021).).
댓글을 작성하려면 로그인해야 합니다.
doju 3년 전 2