제로 포싱 집합 및 네트워크 제어 가능성에 관한 연구—계산 및 엣지 증강

이 기사는 방향이 없는 그래프에서 최소 제로 포싱 집합(ZFS)을 계산하는 문제를 연구하고, 엣지 증강을 통해 최소 ZFS의 크기를 줄이는 새로운 접근 방식을 제시합니다. 최소 ZFS 문제는 여러 응용 프로그램과 관련이 있으며, 예를 들어 그래프에서 정의된 네트워크의 강력한 구조적 제어 가능성에 대한 최소 리더 선택 문제와 관련이 있습니다. 일반적으로 최소 ZFS를 계산하는 것은 NP-hard 문제입니다. ZFS 계산을 위한 탐욕스러운 휴리스틱이 일반적으로 잘 작동하지만, 일부 그래프에 대해서는 임의로 나쁜 솔루션을 제공할 수 있음을 보여줍니다. 우리는 트리에서 최소 ZFS를 계산하기 위한 선형 시간 알고리즘을 제공하고, 클리크 체인 그래프에서 최소 ZFS의 완전한 특성을 제시합니다. 또한 우리는 최소 ZFS 문제를 잠재적 게임으로 형식화하여 일반 그래프에 대한 게임 이론적 솔루션을 제시합니다. 더불어, 엣지 증강이 ZFS 크기에 미치는 영향을 고려합니다. 엣지를 추가하면 네트워크 강건성을 개선할 수 있지만, ZFS의 크기를 늘릴 수 있습니다. 우리는 신중하게 선택된 결측 엣지 집합을 그래프에 추가하는 것이 실제로 최소 ZFS의 크기를 줄일 수 있음을 보여줍니다. 마지막으로, 우리는 랜덤 그래프에서 우리의 결과를 수치적으로 평가합니다.