On Weighted Edge-Searching
Andreas Kolling, Stefano Carpin · 2009
Summary. In this document we address some complications regarding the weighted edge-searching problem. This variant of edge-searching extends the original problem by considering situations where multiple searchers may be required to clear a single edge or guard a single vertex. We show that previous work on this topic overlooked a fundamental problem that arises from the addition of weights. As a consequence, a previously developed algorithm that was thought to compute optimal solutions on trees is in fact not optimal. We describe at which points the proofs are incorrect, provide a counterexample, and point out how to address the problem. 1