Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

References

• Alber J, Betzler N, Niedermeier R (2006) Experiments on data reduction for optimal domination in networks. Ann. Oper. Res. 146(1):105–117.Crossref, Google Scholar
• Alon N, Yuster R, Zwick U (1995) Color-coding. J. ACM 42(4):844–856.Crossref, Google Scholar
• Althaus E, Călinescu G, Mandoiu II, Prasad SK, Tchervenski N, Zelikovsky A (2006) Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks. Wireless Networks 12(3):287–299.Crossref, Google Scholar
• Bentert M, van Bevern R, Nichterlein A, Niedermeier R (2017) Parameterized algorithms for power-efficient connected symmetric wireless sensor networks. Anta AF, Jurdzinski T, Mosteiro MA, Zhang Y, eds. Algorithms Sensor Systems, Lecture Notes in Computer Science, Vol. 10718 (Springer, Berlin), 26–40.Crossref, Google Scholar
• Bentert M, Haag R, Hofer C, Koana T, Nichterlein A (2020a) Parameterized complexity of min-power asymmetric connectivity. Theory Comput. Systems 64(7):1158–1182.Crossref, Google Scholar
• Bentert M, van Bevern R, Fluschnik T, Nichterlein A, Niedermeier R (2020b) Polynomial-time data reduction for weighted problems beyond additive goal functions. Preprint, submitted February 18, https://arxiv.org/abs/1910.00277.Google Scholar
• Betzler N, van Bevern R, Fellows MR, Komusiewicz C, Niedermeier R (2011) Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM Trans. Comput. Biol. Bioinformatics 8(5):1296–1308.Google Scholar
• van Bevern R, Smirnov PV (2020) Optimal-size problem kernels for d-hitting set in linear time and space. Inform. Processing Lett. 163(November):Article 105998.Google Scholar
• van Bevern R, Fluschnik T, Tsidulko OYu (2020) On approximate data reduction for the Rural Postman Problem: Theory and experiments. Networks 76(4):485–508.Crossref, Google Scholar
• van Bevern R, Froese V, Komusiewicz C (2018) Parameterizing edge modification problems above lower bounds. Theory Comput. Systems 62(3):739–770.Crossref, Google Scholar
• van Bevern R, Komusiewicz C, Sorge M (2017) A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments. Networks 70(3):262–278.Crossref, Google Scholar
• Bruckner S, Hüffner F, Karp RM, Shamir R, Sharan R (2010) Topology-free querying of protein interaction networks. J. Comput. Biol. 17(3):237–252.Crossref, Google Scholar
• Călinescu G, Măndoiu II, Zelikovsky A (2002) Symmetric connectivity with minimum power consumption in radio networks. Baeza-Yates R, Montanari U, Santoro N, eds. Foundations of Information Technology in the Era of Network and Mobile Computing, Internat. Federation Inform. Processing, Vol. 96 (Springer, Boston), 119–130.Crossref, Google Scholar
• Carmi P, Katz MJ (2007) Power assignment in radio networks with two power levels. Algorithmica 47(2):183–201.Crossref, Google Scholar
• Chen J, Huang X, Kanj IA, Xia G (2006) Strong computational lower bounds via parameterized complexity. J. Comput. System Sci. 72(8):1346–1367.Crossref, Google Scholar
• Clementi AEF, Penna P, Silvestri R (2004) On the power assignment problem in radio networks. Mobile Network Appl. 9(2):125–140.Crossref, Google Scholar
• Clementi AEF, Huiban G, Penna P, Rossi G, Verhoeven YC (2002) Some recent theoretical advances and open questions on energy consumption in ad-hoc wireless networks. Proc. 3rd Workshop Approximation Randomization Algorithms Comm. Networks, Proceedings in Informatics, Vol. 15 (Carleton Scientific, Waterloo, ON, Canada), 23–38.Google Scholar
• Cygan M, Pilipczuk M, Pilipczuk M, Wojtaszczyk JO (2013) On multiway cut parameterized above lower bounds. ACM Trans. Comput. Theory 5(1):Article 3.Crossref, Google Scholar
• Cygan M, Fomin FV, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized Algorithms (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• de Graaf M, Boucherie RJ, Hurink JL, van Ommeren JCW (2019) An average case analysis of the minimum spanning tree heuristic for the power assignment problem. Random Structures Algorithms 55(1):89–103.Crossref, Google Scholar
• Dost B, Shlomi T, Gupta N, Ruppin E, Bafna V, Sharan R (2008) QNet: A tool for querying protein interaction networks. J. Comput. Biol. 15(7):913–925.Crossref, Google Scholar
• Downey RG, Fellows MR (2013) Fundamentals of Parameterized Complexity (Springer, London).Crossref, Google Scholar
• Erzin AI, Mladenovic N, Plotnikov RV (2017) Variable neighborhood search variants for Min-power symmetric connectivity problem. Comput. Oper. Res. 78(February):557–563.Crossref, Google Scholar
• Erzin AI, Plotnikov RV, Shamardin YV (2013) On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem. J. Appl. Indust. Math. 7(2):142–152.Crossref, Google Scholar
• Flum J, Grohe M (2006) Parameterized Complexity Theory, Texts in Theoretical Computer Science, an EATCS Series (Springer, Berlin).Google Scholar
• Fomin FV, Lokshtanov D, Saurabh S, Zehavi M (2019) Kernelization (Cambridge University Press, Cambridge, UK).Google Scholar
• Garg S, Philip G (2016) Raising the bar for vertex cover: Fixed-parameter tractability above a higher guarantee. Kraughgamer R, ed. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1152–1166.Google Scholar
• Gutin G, Wahlstrom M, Yeo A (2017) Rural Postman parameterized by the number of components of required edges. J. Comput. System Sci. 83(1):121–131.Google Scholar
• Hermelin D, Kratsch S, Sołtys K, Wahlström M, Wu X (2015) A completeness theory for polynomial (Turing) kernelization. Algorithmica 71(3):702–730.Crossref, Google Scholar
• Hoffmann S, Kampermann T, Wanke E (2018) Minimizing the number of max-power users in ad-hoc wireless networks with minimum node degree requirements. Inform. Process. Lett. 136(August):25–29.Crossref, Google Scholar
• Impagliazzo R, Paturi R (2001) On the complexity of k-SAT. J. Comput. System Sci. 62(2):367–375.Google Scholar
• Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J. Comput. System Sci. 63(4):512–530.Crossref, Google Scholar
• Kirousis LM, Kranakis E, Krizanc D, Pelc A (2000) Power consumption in packet radio networks. Theoret. Comput. Sci. 243(1):289–305.Crossref, Google Scholar
• Mahajan M, Raman V (1999) Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2):335–354.Google Scholar
• Mellor D, Prieto E, Mathieson L, Moscato P (2010) A kernelisation approach for multiple d-hitting set and its application in optimal multi-drug therapeutic combinations. PLoS One 5(10):e13055.Crossref, Google Scholar
• Montemanni R, Gambardella L (2005) Exact algorithms for the minimum power symmetric connectivity problem in wireless networks. Comput. Oper. Res. 32(11):2891–2904.Crossref, Google Scholar
• Niedermeier R (2006) Invitation to Fixed-Parameter Algorithms (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• Panigrahi D (2011) Survivable network design problems in wireless networks. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1014–1027.Google Scholar
• Perlin K, Hoffert EM (1989) Hypertexture. Comput. Graph. 23(3):253–262.Crossref, Google Scholar
• Plotnikov R, Erzin A, Mladenovic N (2019) VNDS for the min-power symmetric connectivity problem. Optim. Lett. 13(8):1897–1911.Crossref, Google Scholar
• Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. Leighton FT, Shor PW, eds. Proc. 29th Annual ACM Sympos. Theory Comput. (ACM, New York), 475–484.Google Scholar
• Rodoplu V, Meng TH (1999) Minimum energy mobile wireless networks. IEEE J. Selected Areas Comm. 17(8):1333–1344.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics, Vol. 24 (Springer, Berlin).Google Scholar
• Scott J, Ideker T, Karp RM, Sharan R (2006) Efficient algorithms for detecting signaling pathways in protein interaction networks. J. Comput. Biol. 13(2):133–144.Crossref, Google Scholar
• Smirnov PV (2020) Razrabotka algoritmov i programmnogo obespecheniya dlya resheniya zadach analiza setevykh struktur [Algorithm and software design for network analysis problems]. Master’s thesis, Novosibirsk State University, Novosibirsk, Russian Federation.Google Scholar
• Sorge M, van Bevern R, Niedermeier R, Weller M (2011) From few components to an Eulerian graph by adding arcs. Kolman P, Kratochvıl J, eds. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, Vol. 6986 (Springer, Berlin), 307–318.Crossref, Google Scholar
• Sorge M, van Bevern R, Niedermeier R, Weller M (2012) A new view on Rural Postman based on Eulerian Extension and Matching. J. Discrete Algorithms 16(October):12–33.Crossref, Google Scholar
• Williamson DP, Shmoys DB (2011) The Design of Approximation Algorithms (Cambridge University Press, New York).Crossref, Google Scholar
• Zalyubovskiy VV, Erzin AI, Astrakov SN, Choo H (2009) Energy-efficient area coverage by sensors with adjustable ranges. Sensors (Basel) 9(4):2446–2460.Crossref, Google Scholar
• Zhang H, Hou JC (2005) Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sensor Wireless Networks 1(1–2):89–124.Google Scholar