Abstract
We investigate multivariate algorithms for the NP-hard Min-Power Asymmetric Connectivity (MinPAC) problem that has applications in wireless sensor networks. Given a directed arc-weighted n-vertex graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W[2]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.
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
Bai, X., Kumar, S., Xuan, D., Yun, Z., Lai, T.: Deploying wireless sensors to achieve both coverage and connectivity. In: Proceedings of MobiHoc 2006, pp. 131–142. ACM (2006)
Bentert, M., van Bevern, R., Nichterlein, A., Niedermeier, R.: Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 26–40. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72751-6_3
Călinescu, G.: Approximate min-power strong connectivity. SIAM J. Discrete Math. 27(3), 1527–1543 (2013)
Călinescu, G.: 1.61-approximation for min-power strong connectivity with two power levels. J. Comb. Optim. 31(1), 239–259 (2016)
Calinescu, G., Kapoor, S., Olshevsky, A., Zelikovsky, A.: Network lifetime and power assignment in ad hoc wireless networks. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 114–126. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39658-1_13
Carmi, P., Katz, M.J.: Power assignment in radio networks with two power levels. Algorithmica 47(2), 183–201 (2007)
Chen, J., Lu, H., Kuo, T., Yang, C., Pang, A.: Dual power assignment for network connectivity in wireless sensor networks. In: Proceedings of GLOBECOM 2005, p. 5. IEEE (2005)
Chen, W., Huang, N.: The strongly connecting problem on multihop packet radio networks. IEEE Trans. Commun. 37(3), 293–295 (1989)
Clementi, A.E.F., Penna, P., Silvestri, R.: On the power assignment problem in radio networks. MONET 9(2), 125–140 (2004)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Heidelberg (2013). https://doi.org/10.1007/978-1-4471-5559-1
Etscheid, M., Kratsch, S., Mnich, M., Röglin, H.: Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84, 1–10 (2017)
Fellows, M.R., Gaspers, S., Rosamond, F.A.: Parameterizing by the number of numbers. Theory Comput. Syst. 50(4), 675–693 (2012)
Impagliazzo, R., Paturi, R.: On the complexity of \(k\)- SAT. J. Comput. Syst. Sci. 62(2), 21 (2001)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)
Iyengar, R., Kar, K., Banerjee, S.: Low-coordination topologies for redundancy in sensor networks. In: Proceedings of MobiHoc 2005, pp. 332–342. ACM (2005)
Rong, Y., Choi, H., Choi, H.: Dual power management for network connectivity in wireless sensor networks. In: Proceedings of IPDPS 2004. IEEE (2004)
Sorge, M., Van Bevern, R., Niedermeier, R., Weller, M.: A new view on rural postman based on Eulerian extension and matching. J. Discrete Algorithms 16, 12–33 (2012)
Zhang, H., Hou, J.C.: Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sensor Wirel. Netw. 1, 89–124 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Bentert, M., Haag, R., Hofer, C., Koana, T., Nichterlein, A. (2019). Parameterized Complexity of Min-Power Asymmetric Connectivity. In: Colbourn, C., Grossi, R., Pisanti, N. (eds) Combinatorial Algorithms. IWOCA 2019. Lecture Notes in Computer Science(), vol 11638. Springer, Cham. https://doi.org/10.1007/978-3-030-25005-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-25005-8_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-25004-1
Online ISBN: 978-3-030-25005-8
eBook Packages: Computer ScienceComputer Science (R0)