지배적 인 세트의 최대 커버리지 버전

Question

지배적 인 설정 문제는 다음과 같습니다.

$ n $ 버텍스 그래프 $ g= (v, e) $ , $ | n [s] | $ 이 정확히 $ s (\ subetq v) $ 을 설정하십시오. SPAN 클래스="수학 컨테이너"> $ n $ , 여기서 $$ n [s] :={x ~ | \ text {$ x $ / $ x $ lies의 이웃 $ s $} \} $$

내 질문은 다음 (새로운 문제)이 문헌에 명확한 이름을 가지고 있고 가장 적절한 이름이 아닌 경우

새 문제 : $ n $ 정점 그래프 $ g= (v, e) $ 및 정수 $ k $ , 세트 $ s (\ subeteq v) $ < / span> $ k $ $ | n [s] | $ 이 최대화됩니다. < / P>

두 번째 문제에 대해서는 내가 문헌에서 본 이름 중 일부는 최대 그래프 적용 범위입니다. 부분 적용 범위; K-Deannating-set, (그러나 동일한 이름은 다른 컨텍스트에서도 사용됩니다).

Answer 1

$ k $ 정점을 선택 해야하는 문제점을 최대화하려면 예산이 지배적 인 설정 문제 으로 알려져 있습니다. ...에 문제 또는 그 연결된 변형은 적어도 Lamprou, Sigalis 및 Zissimopoulos [1] 및 Khuller, Purohit 및 Sarpatwar [2]에 의해 연구됩니다. 또한 Narayanaswamy 및 Vijayaragunathan [3]의 최근 조사에도 나타납니다.

---

[1] Lamprou, Ioannis, Ioannis Sigalas, Vassilis Zissimopoulos. "개선 된 책정 된 지배 및 예산 엣지 - 꼭지점 지배." ARXIV PrePrint Arxiv : 1907.06576 (2019).

[2] Khuller, Samir, Manish Purohit 및 Kanthi K. Sarpatwar. "최적의 이웃 분석 : 예산 및 부분 연결된 지배적 인 문제점을위한 알고리즘." 이산 알고리즘에 25 번째 연례 ACM-SIAM 심포지움의 절차. 산업 및 응용 수학 사회, 2014.

[3] Narayanaswamy, N. S. 및 R. vijayaragunathan. "불확실한 그래프의 매개 변수화 된 최적화 - 설문 조사 및 일부 결과." 알고리즘 13.1 (2020) : 3.