Approximation Algorithms for Dominating Set in Disk Graphs

論文紹介

Matt Gibson, Imran A. Pirwani
http://arxiv.org/abs/1004.3320

平面上のdiskのintersectionグラフにおける最小支配集合問題がPTASを持つかどうかは大きな未解決問題であったが，この論文はそれを肯定的に解決している．去年のSoCGでChan & Har-PeledとMustafa & Rayが独立に提案した局所探索の枠組を使っている．ボロノイ図に着目したところがよかったんだと思う．