Abstract
Line of Sight (LoS) networks were designed to model wireless networks in settings which may contain obstacles restricting visibility of sensors. A graph \(G=(V,E)\) is a 2-dimensional LoS network if it can be embedded in an \(n \times k\) rectangular point set such that a pair of vertices in V are adjacent if and only if the embedded vertices are placed on the same row or column and are at a distance less than \(\omega \). We study the Maximum Independent Set (MIS) problem in restricted LoS networks where k is a constant. It has been shown in the unrestricted case when \(n=k\) and \(n\rightarrow \infty \) that the MIS problem is NP-hard when \( \omega > 2\) is fixed or when \(\omega =O(n^{1-\epsilon })\) grows as a function of n for fixed \(0<\epsilon <1\). In this paper we develop a dynamic programming (DP) algorithm which shows that in the restricted case the MIS problem is solvable in polynomial time for all \(\omega \). We then generalise the DP algorithm to solve three additional problems which involve two versions of the Maximum Weighted Independent Set (MWIS) problem and a scheduling problem which exhibits LoS properties in one dimension. We use the initial DP algorithm to develop an efficient polynomial time approximation scheme (EPTAS) for the MIS problem in restricted LoS networks. This has important applications, as it provides a semi-online solution to a particular instance of the scheduling problem. Finally we extend the EPTAS result to the MWIS problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albers, S.: Online algorithms: a survey. Math. Program. 97(1–2), 3–26 (2003)
Bellman, R., Esogbue, A.O., Nabeshima, I.: Mathematical Aspects of Scheduling and Applications. Elsevier, Amsterdam (2014)
Bollobás, B., Janson, S., Riordan, O.: Line-of-sight percolation. Comb. Probab. Comput. 18(1–2), 83–106 (2009)
Cesati, M., Trevisan, L.: On the efficiency of polynomial time approximation schemes. Inf. Process. Lett. 64(4), 165–171 (1997)
Chiu, S.N., Stoyan, D., Kendall, W.S., Mecke, J.: Stochastic Geometry and Its Applications. Wiley, Hoboken (2013)
Czumaj, A., Wang, X.: Communication problems in random line-of-sight ad-hoc radio networks. In: Hromkovič, J., Královič, R., Nunkesser, M., Widmayer, P. (eds.) SAGA 2007. LNCS, vol. 4665, pp. 70–81. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74871-7_7
Diestel, R.: Graph Theory. Springer, New York (2000)
Farczadi, L., Devroye, L.: Connectivity for line-of-sight networks in higher dimensions. Discret. Math. Theor. Comput. Sci. 15 (2013)
Frieze, A., Kleinberg, J., Ravi, R., Debany, W.: Line-of-sight networks. Comb. Probab. Comput. 18(1–2), 145–163 (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)
Håstad, J.: Clique is hard to approximate within \(n^{1-\varepsilon }\). Acta Math. 182, 105–142 (1999)
Sangha, P., Zito, M.: Finding large independent sets in line of sight networks. In: Gaur, D., Narayanaswamy, N.S. (eds.) CALDAM 2017. LNCS, vol. 10156, pp. 332–343. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53007-9_29
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Sangha, P., Wong, P.W.H., Zito, M. (2017). Independent Sets in Restricted Line of Sight Networks. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M., Zhang, Y. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2017. Lecture Notes in Computer Science(), vol 10718. Springer, Cham. https://doi.org/10.1007/978-3-319-72751-6_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-72751-6_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-72750-9
Online ISBN: 978-3-319-72751-6
eBook Packages: Computer ScienceComputer Science (R0)