Secluded Path via Shortest Path

摘要: We provide several new algorithmic results for the secluded path problem, specifically approximation and optimality static algorithm of [3,5], an extension (h-Memory) it based on de Bruijn graphs, when applied to bounded degree graphs some other special graph classes which can model wireless communication line-of-sight settings. Our primary result is that h-Memory a PTAS degree-Δ unweighted, undirected providing \(\lceil{\sqrt{{\Delta+1}\over{h+1}}}\rceil\)-approximation in time O(n logn); particular, 0-Memory (i.e., static) provides \(\sqrt{\Delta+1}\) -approximation \(\epsilon=\sqrt{\Delta+1}-1\)), tightening previous analysis this algorithm, Δ-Memory optimal e = 0), faster than known setting [3].