Fixed parameter tractable algorithms for watchman route related problems on line segment arrangements

References

• M.H. Alsuwaiyel and D. Lee, Minimal link visibility paths inside a simple polygon, Comput. Geom. 3 (1993), pp. 1–25. Available at https://www.sciencedirect.com/science/article/pii/0925772193900274.
   Web of Science ®Google Scholar
• M.H. Alsuwaiyel and D. Lee, Finding an approximate minimum-link visibility path inside a simple polygon, Inf. Process. Lett. 55 (1995), pp. 75–79. Available at https://www.sciencedirect.com/science/article/pii/002001909500072K.
   Web of Science ®Google Scholar
• E.M. Arkin, J.S.B. Mitchell, and C.D. Piatko, Minimum-link watchman tours, Inf. Process. Lett. 86 (2003), pp. 203–207. Available at https://api.semanticscholar.org/CorpusID:16064699.
   Web of Science ®Google Scholar
• A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Fourier meets möbius: fast subset convolution, in Symposium on the Theory of Computing, 2006. Available at https://api.semanticscholar.org/CorpusID:15119557.
   Google Scholar
• H.L. Bodlaender, C. Feremans, A. Grigoriev, E. Penninkx, R. Sitters, and T. Wolle, On the minimum corridor connection problem and other generalized geometric problems, Comput. Geom. 42 (2009), pp. 939–951. Available at https://www.sciencedirect.com/science/article/pii/S0925772109000741.
   Web of Science ®Google Scholar
• V.E. Brimkov, A. Leach, M. Mastroianni, and J. Wu, Guarding a set of line segments in the plane, Theor. Comput. Sci. 412 (2011), pp. 1313–1324. Available at https://www.sciencedirect.com/science/article/pii/S0304397510004494, Theoretical Computer Science Issues in Image Analysis and Processing.
   Web of Science ®Google Scholar
• W.P. Chin and S. Ntafos, Shortest watchman routes in simple polygons, Discrete Comput. Geom. 6 (1991), pp. 9–31. Available at https://rdcu.be/dvZyB.
   Web of Science ®Google Scholar
• M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, 1st ed., Springer Publishing Company, Cham, Switzerland, 2015. Available at https://doi.org/10.1007/978-3-319-21275-3.
   Google Scholar
• S.E. Dreyfus and R.A. Wagner, The Steiner problem in graphs, Networks 1 (1971), pp. 195–207. Available at https://doi.org/10.1002/net.3230010302
   Google Scholar
• M. Dror, A. Efrat, A. Lubiw, and J.S. Mitchell, Touring a sequence of polygons, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 473–482.
   Google Scholar
• A. Dumitrescu, J.S. Mitchell, and P. Żyliński, Watchman routes for lines and segments, in Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 7357, F.V. Fomin and P. Kaski, eds., Springer, Berlin, 2012, pp. 36–47.
   Google Scholar
• A. Dumitrescu, J.S. Mitchell, and P. Żyliński, The minimum guarding tree problem, Discrete Math. Algor. Appl. 6 (2014), article number 14500116. https://api.semanticscholar.org/CorpusID:1362744.
   Google Scholar
• A. Feldmann and D. Marx. The complexity landscape of fixed-parameter directed Steiner network problems, ACM Trans. Comput. Theory 15 (2023), pp. 1-28. Available at https://doi.org/10.1145/3580376.
   Google Scholar
• M.R. Garey, R.L. Graham, and D.S. Johnson, Some NP-complete geometric problems, in Proceedings of the 8th annual ACM Symposium on Theory of Computing. ACM, 1976, pp. 10–22.
   Google Scholar
• J. Guo, R. Niedermeier, and S. Wernicke, Parameterized complexity of vertex cover variants, Theor. Comput. Syst. 41 (2007), pp. 501–520.
   Web of Science ®Google Scholar
• N. Misra, G. Philip, V. Raman, S. Saurabh, and S. Sikdar, FPT algorithms for connected feedback vertex set, J. Comb. Optim. 24 (2012), pp. 131–146.
   Web of Science ®Google Scholar
• J. Nederlof, Fast polynomial-space algorithms using möbius inversion: Improving on Steiner tree and related problems, in International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 5555, S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, and W. Thomas, eds., Springer, Berlin, 2009, pp. 713-725. Available at https://doi.org/10.1007/978-3-642-02927-1_59.
   Google Scholar
• J. Nederlof, Fast polynomial-space algorithms using inclusion-exclusion, Algorithmica 65 (2013), pp. 868–884. Available at https://doi.org/10.1007/s00453-012-9630-x.
   Web of Science ®Google Scholar
• W. Pang Chin and S. Ntafos, Optimum watchman routes, Inf. Process. Lett. 28 (1988), pp. 39–44. Available at https://www.sciencedirect.com/science/article/pii/002001908890141X.
   Web of Science ®Google Scholar
• M. Rema, R. Subashini, S. Methirumangalath, and V. Rajan, Classical and parameterized complexity of line segment covering problems in arrangement, in Intelligent Data Engineering and Analytics, V. Bhateja, F. Carroll, J.M.R.S. Tavares, S.S. Sengar, and P. Peer, eds., Springer Nature Singapore, Singapore, 2023, pp. 327–338.
   Google Scholar
• X. Tan and T. Hirata, Constructing shortest watchman routes by divide-and-conquer, in International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 762, K.W. Ng, P. Raghavan, N.V. Balasubramanian, and F.Y.L. Chin, eds., Springer, Berlin, 1993, pp. 68–77. Available at https://doi.org/10.1007/3-540-57568-5_236.
   Google Scholar
• X. Tan, T. Hirata, and Y. Inagaki, An incremental algorithm for constructing shortest watchman routes, Int. J. Comput. Geom. Appl. 3 (1993), pp. 351–365.
   Google Scholar
• N. Xu, Complexity of minimum corridor guarding problems, Inf. Process. Lett. 112 (2012), pp. 691–696. Available at https://www.sciencedirect.com/science/article/abs/pii/S0020019012001433.
   Web of Science ®Google Scholar