{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:28Z","timestamp":1771036348001,"version":"3.50.1"},"reference-count":31,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2020,1,26]],"date-time":"2020-01-26T00:00:00Z","timestamp":1579996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["691161"],"award-info":[{"award-number":["691161"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>As technology advances and the spreading of wireless devices grows, the establishment of interconnection networks is becoming crucial. Main activities that involve most of the people concern retrieving and sharing information from everywhere. In heterogeneous networks, devices can communicate by means of multiple interfaces. The choice of the most suitable interfaces to activate (switch-on) at each device results in the establishment of different connections. A connection is established when at its endpoints the devices activate at least one common interface. Each interface is assumed to consume a specific percentage of energy for its activation. This is referred to as the cost of an interface. Due to energy consumption issues, and the fact that most of the devices are battery powered, special effort must be devoted to suitable solutions that prolong the network lifetime. In this paper, we consider the so-called p-Coverage problem where each device can activate at most p of its available interfaces in order to establish all the desired connections of a given network of devices. As the problem has been shown to be    NP   -hard even for     p = 2     and unitary costs of the interfaces, algorithmic design activities have focused in particular topologies where the problem is optimally solvable. Following this trend, we first show that the problem is polynomially solvable for graphs (modeling the underlying network) of bounded treewidth by means of the Courcelle\u2019s theorem. Then, we provide two optimal polynomial time algorithms to solve the problem in two subclasses of graphs with bounded treewidth that are graphs of bounded pathwidth and graphs of bounded carvingwidth. The two solutions are obtained by means of dynamic programming techniques.<\/jats:p>","DOI":"10.3390\/a13020031","type":"journal-article","created":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T07:41:11Z","timestamp":1580110871000},"page":"31","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Constrained Connectivity in Bounded X-Width Multi-Interface Networks"],"prefix":"10.3390","volume":"13","author":[{"given":"Alessandro","family":"Aloisio","sequence":"first","affiliation":[{"name":"Department of Information Engineering, Computer Science and Maths, University of L\u2019Aquila; School of Advanced Studies, Gran Sasso Science Institute, 67100 L\u2019Aquila, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8547-5934","authenticated-orcid":false,"given":"Alfredo","family":"Navarra","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Perugia, 06123 Perugia, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2020,1,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1002\/net.20266","article-title":"Cost Minimization in Wireless Networks with a Bounded and Unbounded Number of Interfaces","volume":"53","author":"Klasing","year":"2009","journal-title":"Networks"},{"key":"ref_2","unstructured":"Aloisio, A., and Navarra, A. (2015, January 24\u201329). Balancing energy consumption for the establishment of multi-interface networks. Proceedings of the 41st International Conference on Current Trends in Theory and Practice of Computer Science, (SOFSEM), Pec pod Sn\u011b\u017ekou, Czech Republic."},{"key":"ref_3","unstructured":"Aloisio, A., Navarra, A., and Mostarda, L. (March, January 27\u2013). Distributing energy consumption in multi-interface series-parallel networks. Proceedings of the 5th IEEE AINA International Workshop on Engineering Energy Efficient Internetworked Smart Sensor (E3WSN), Matsue, Japan."},{"key":"ref_4","first-page":"1","article-title":"Energy Consumption Balancing in Multi-Interface Networks","volume":"2019","author":"Aloisio","year":"2020","journal-title":"J. Ambient. Intell. Humaniz. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Aloisio, A., and Navarra, A. (2020). Budgeted Constrained Coverage on Series-Parallel Multi-Interface Networks. Proceedings of the 34th International Conference on Advanced Information Networking and Applications (AINA-2020), Springer. to appear.","DOI":"10.1007\/978-3-030-44041-1_41"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/1039111.1039122","article-title":"Reconsidering wireless systems with multiple radios","volume":"5","author":"Bahl","year":"2004","journal-title":"SIGCOMM Comput. Commun. Rev."},{"key":"ref_7","unstructured":"Ibrahiem, S.R., and El Emary, M.M. (2013). Multi-interface wireless networks: Complexity and algorithms. Wireless Sensor Networks: From Theory to Applications, Taylor & Francis Group."},{"key":"ref_8","unstructured":"Draves, R., Padhye, J., and Zill, B. (October, January 26). Routing in multi-radio, multi-hop wireless mesh networks. Proceedings of the of the 10th International Conference on Mobile Computing and Networking (MobiCom), Philadelphia, PA, USA."},{"key":"ref_9","unstructured":"Cavalcanti, D., Gossain, H., and Agrawal, D. (2005, January 11\u201314). Connectivity in multi-radio, multi-channel heterogeneous ad hoc networks. Proceedings of the 16th International Symp. on Personal, Indoor and Mobile Radio Communications (PIMRC), Berlin, Germany."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Caporuscio, M., Charlet, D., Issarny, V., and Navarra, A. (2007, January 5\u20138). Energetic Performance of Service-oriented Multi-radio Networks: Issues and Perspectives. Proceedings of the of the 6th International Workshop on Software and Performance (WOSP), Buenes Aires, Argentina.","DOI":"10.1145\/1216993.1217002"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/s00453-011-9531-4","article-title":"Minimize the maximum duty in multi-interface networks","volume":"63","author":"Navarra","year":"2012","journal-title":"Algorithmica"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/s00224-012-9384-5","article-title":"Energy-efficient communication in multi-interface wireless networks","volume":"52","author":"Athanassopoulos","year":"2013","journal-title":"Theory Comput. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1007\/s11276-009-0188-8","article-title":"Exploiting Multi-Interface Networks: Connectivity and Cheapest Paths","volume":"16","author":"Kosowski","year":"2010","journal-title":"Wirel. Netw."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.tcs.2013.01.018","article-title":"Maximum matching in multi-interface networks","volume":"507","author":"Kosowski","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.jda.2017.07.002","article-title":"Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks","volume":"45","author":"Audrito","year":"2017","journal-title":"J. Discret. Algorithms"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1109\/TC.2012.214","article-title":"Flow problems in multi-interface networks","volume":"63","author":"Navarra","year":"2014","journal-title":"IEEE Trans. Comput."},{"key":"ref_17","unstructured":"Aloisio, A., Autili, M., D\u2019Angelo, A., Viidanoja, A., Leguay, J., Ginzler, T., Lampe, T., Spagnolo, L., Wolthusen, S., and Flizikowski, A. (2014, January 22\u201323). TACTICS: tactical service oriented architecture. Proceedings of the 3rd International Conference in Software Engineering for Defence Applications, Rome, Italy."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Perucci, A., Autili, M., Tivoli, M., Aloisio, A., and Inverardi, P. (2018, January 7\u20138). Distributed composition of highly-collaborative services and sensors in tactical domains. Proceedings of the of 6th International Conference in Software Engineering for Defence Applications (SEDA), Rome, Italy.","DOI":"10.1007\/978-3-030-14687-0_21"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.disopt.2010.10.002","article-title":"Cutting stock with no three parts per pattern: Work-in-process and pattern minimization","volume":"8","author":"Aloisio","year":"2011","journal-title":"Discret. Optim."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., and Kratsch, D. (2010). Exact Exponential Algorithms, Springer.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inf. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(95)00190-5","article-title":"A Simple Linear-Time Algorithm for Finding Path-Decompositions of Small Width","volume":"57","author":"Cattell","year":"1996","journal-title":"Inf. Process. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A linear time algorithm for finding tree-decompositions of small treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1888","DOI":"10.1016\/j.dam.2013.02.036","article-title":"Characterizing graphs of small carving-width","volume":"161","author":"Belmonte","year":"2013","journal-title":"Discret. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Thilikos, D., Serna, M., and Bodlaender, H. (2000, January 18\u201320). Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width. Proceedings of the 11th International Conference on Algorithms and Computation (ISAAC), Taipei, Taiwan.","DOI":"10.1007\/3-540-40996-3_17"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1002\/net.20422","article-title":"On LP relaxations for the pattern minimization problem","volume":"57","author":"Aloisio","year":"2011","journal-title":"Networks"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Flammini, M., Moscardelli, L., Navarra, A., and P\u00e9rennes, S. (2005, January 26\u201329). Asymptotically optimal solutions for small world graphs. Proceedings of the 19th International Conference on Distributed Computing (DISC), Cracow, Poland.","DOI":"10.1007\/11561927_30"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Angelini, P., Eades, P., Hong, S., Klein, K., Kobourov, S.G., Liotta, G., Navarra, A., and Tappini, A. (2018, January 26\u201328). Turning cliques into paths to achieve planarity. Proceedings of the 26th International Symp. on Graph Drawing and Network Visualization GD, Barcelona, Spain.","DOI":"10.1007\/978-3-030-04414-5_5"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1002\/net.20293","article-title":"On the complexity of distributed graph coloring with local minimality constraints","volume":"54","author":"Gavoille","year":"2009","journal-title":"Networks"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1016\/j.jda.2011.12.007","article-title":"Distributed colorings for collision-free routing in sink-centric sensor networks","volume":"14","author":"Navarra","year":"2012","journal-title":"J. Discret. Algorithms"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1016\/j.adhoc.2007.06.003","article-title":"3-Dimensional minimum energy broadcasting problem","volume":"6","author":"Navarra","year":"2008","journal-title":"Ad Hoc Netw."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/31\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:08:35Z","timestamp":1760364515000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/2\/31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,26]]},"references-count":31,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,2]]}},"alternative-id":["a13020031"],"URL":"https:\/\/doi.org\/10.3390\/a13020031","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,26]]}}}