Parameterized complexity of min-power asymmetric connectivity. (English) Zbl 1503.68080
Summary: We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-weighted 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 in the chosen subgraph. 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.
MSC:
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 05C22 | Signed and weighted graphs |
| 05C40 | Connectivity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68M18 | Wireless sensor networks as related to computer science |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W05 | Nonnumerical algorithms |
References:
| [1] | Bai, X., Kumar, S., Xuan, D., Yun, Z., Lai, T.-H.: Deploying wireless sensors to achieve both coverage and connectivity. In: Proceedings of the 7th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 06), pp. 131-142. ACM (2006) |
| [2] | Bentert, M., van Bevern, R., Nichterlein, A., Niedermeier, R.: Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. In: Proceedings of the 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS ’17), volume 10718 of LNCS, pp. 26-40. Springer (2017) · Zbl 1503.68026 |
| [3] | Bentert, M., Van Bevern, R., Fluschnik, T., Nichterlein, A., Niedermeier, R.: Polynomial-time preprocessing for weighted problems beyond additive goal functions. CoRR, arXiv:abs/1910.00277 (2019) |
| [4] | Călinescu, G., Approximate min-power strong connectivity, SIAM J. Discrete Math., 27, 3, 1527-1543 (2013) · Zbl 1278.05133 · doi:10.1137/100819540 |
| [5] | Călinescu, G., 1.61-approximation for min-power strong connectivity with two power levels, J. Comb. Optim., 31, 1, 239-259 (2016) · Zbl 1341.90133 · doi:10.1007/s10878-014-9738-9 |
| [6] | Călinescu, G., Kapoor, S., Olshevsky, A., Zelikovsky, A.: Network lifetime and power assignment in ad hoc wireless networks. In: Proceedings of the 11th Annual European Symposium on Algorithms (ESA ’03), volume 2832 of LNCS, pp. 114-126. Springer (2003) · Zbl 1266.68022 |
| [7] | Carmi, P.; Katz, MJ, Power assignment in radio networks with two power levels, Algorithmica, 47, 2, 183-201 (2007) · Zbl 1108.90015 · doi:10.1007/s00453-006-1230-1 |
| [8] | Chen, J.-J., Lu, H.-I., Kuo, T.-W., Yang, C.-Y., Pang, A.-C.: Dual power assignment for network connectivity in wireless sensor networks. In: Proceedings of the Global Telecommunications Conference (GLOBECOM T’05), pp. 5. IEEE (2005) |
| [9] | Chen, W-T; Huang, N-F, The strongly connecting problem on multihop packet radio networks, IEEE Trans. Commun., 37, 3, 293-295 (1989) · doi:10.1109/26.20105 |
| [10] | Clementi, AEF; Penna, P.; Silvestri, R., On the power assignment problem in radio networks, Mobile Netw. Appl., 9, 2, 125-140 (2004) · doi:10.1023/B:MONE.0000013624.32948.87 |
| [11] | Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Springer (2013) · Zbl 1358.68006 |
| [12] | Fellows, MR; Gaspers, S.; Rosamond, FA, Parameterizing by the number of numbers, Theor. Comput. Syst., 50, 4, 675-693 (2012) · Zbl 1253.68173 |
| [13] | Impagliazzo, R.; Paturi, R., On the complexity of k-SAT, J. Comput. Syst. Sci., 62, 2, 21 (2001) · Zbl 0990.68079 |
| [14] | Impagliazzo, R.; Paturi, R.; Zane, F., Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052 |
| [15] | Iyengar, R.; Kar, K.; Banerjee, S., Low-coordination wake-up algorithms for multiple connected-covered topologies in sensor nets, Int. J. Sens. Netw., 5, 1, 33-47 (2009) |
| [16] | Rong, Y., Choi, H., Choi, H.-A.: Dual power management for network connectivity in wireless sensor networks. In: Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS ’04), IEEE (2004) |
| [17] | 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) · Zbl 1255.68076 · doi:10.1016/j.jda.2012.04.007 |
| [18] | Zhang, H., Hou, J.C.: Maintaining sensing coverage and connectivity in large sensor networks. In: Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-To-Peer Networks, pp. 453-474. CRC Press / Taylor & Francis (2005) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
