{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T11:04:37Z","timestamp":1767092677650,"version":"3.41.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T00:00:00Z","timestamp":1515542400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00224-017-9836-z","type":"journal-article","created":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T06:57:56Z","timestamp":1515567476000},"page":"1673-1689","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximation and Heuristic Algorithms for Computing Backbones in Asymmetric Ad-hoc Networks"],"prefix":"10.1007","volume":"62","author":[{"given":"Faisal N.","family":"Abu-Khzam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2689-4412","authenticated-orcid":false,"given":"Christine","family":"Markarian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm Meyer auf der","family":"Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Schubert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,1,10]]},"reference":[{"key":"9836_CR1","doi-asserted-by":"crossref","unstructured":"Abu-Khzam, F., Markarian, C.: A degree-based heuristic for strongly connected dominating-absorbent sets in wireless ad-hoc networks. In: Innovations in Information Technology, pp. 200\u2013204 (2012)","DOI":"10.1109\/INNOVATIONS.2012.6207732"},{"key":"9836_CR2","doi-asserted-by":"crossref","unstructured":"Markarian, C., Meyer auf der Heide, F., Schubert, M.: A distributed approximation algorithm for strongly connected dominating-absorbent sets in asymmetric wireless ad-hoc networks. In: ALGOSENSORS, pp. 217\u2013227 (2013)","DOI":"10.1007\/978-3-642-45346-5_16"},{"key":"9836_CR3","unstructured":"Cardei, M., Cheng, X., Cheng, X., Zhu Du, D.: Connected domination in multihop ad-hoc wireless networks. In: International Conference on Computer Science and Informatics, pp. 251\u2013255 (2002)"},{"issue":"9","key":"9836_CR4","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1109\/TPDS.2002.1036062","volume":"13","author":"J Wu","year":"2004","unstructured":"Wu, J.: Extended dominating-set-based routing in ad-hoc wireless networks with unidirectional links. IEEE Trans. Parallel Distrib. Syst. 13(9), 866\u2013881 (2004)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"1","key":"9836_CR5","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1109\/JCN.2002.6596934","volume":"4","author":"J Wu","year":"2002","unstructured":"Wu, J., Dai, F., Gao, M., Stojmenovic, I.: On calculating power-aware connected dominating sets for efficient routing in ad-hoc wireless networks. IEEE Journal of Communications and Networks 4(1), 59\u201370 (2002)","journal-title":"IEEE Journal of Communications and Networks"},{"key":"9836_CR6","doi-asserted-by":"crossref","unstructured":"Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: International Conference on Communications, pp. 376\u2013380 (1997)","DOI":"10.1109\/ICC.1997.605303"},{"key":"9836_CR7","doi-asserted-by":"crossref","unstructured":"Das, B., Sivakumar, R., Bharghavan, V.: Routing in ad-hoc networks using a spine. In: International Conference on Computers and Communication Networks, pp. 34\u201339 (1997)","DOI":"10.1109\/ICCCN.1997.623288"},{"issue":"10","key":"9836_CR8","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1109\/TPDS.2004.48","volume":"15","author":"F Dai","year":"2004","unstructured":"Dai, F., Wu, J.: An Extended Localized Algorithm for Connected Dominating Set Formation in Ad-hoc Wireless Networks. IEEE Trans. Parallel Distrib. Syst. 15 (10), 908\u2013920 (2004)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9836_CR9","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set algorithm for growth-bounded graphs. In: Principles of Distributed Computing, pp. 35\u201344 (2008)","DOI":"10.1145\/1400751.1400758"},{"key":"9836_CR10","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B Clark","year":"1990","unstructured":"Clark, B., Colbourn, C., Johnson, D.: Unit disk graphs. Discret. Math. 86, 165\u2013177 (1990)","journal-title":"Discret. Math."},{"key":"9836_CR11","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1007\/978-3-540-87779-0_27","volume":"5218","author":"C Lenzen","year":"2008","unstructured":"Lenzen, C., Wattenhofer, R.: Leveraging Linial\u2019s locality limit. Distrib. Comput. 5218, 394\u2013407 (2008)","journal-title":"Distrib. Comput."},{"issue":"1","key":"9836_CR12","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1504\/IJESMS.2015.066127","volume":"7","author":"AK Yadav","year":"2015","unstructured":"Yadav, A.K., Yadav, R.S., Singh, R., Singh, A.K.: Connected dominating set for wireless ad hoc networks: a survey. International Journal of Engineering Systems Modelling and Simulation 7(1), 22\u201334 (2015)","journal-title":"International Journal of Engineering Systems Modelling and Simulation"},{"issue":"2","key":"9836_CR13","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/j.comcom.2012.10.005","volume":"36","author":"J Yu","year":"2013","unstructured":"Yu, J., Wang, N., Wang, G., Yu, D.: Connected dominating sets in wireless ad hoc and sensor networks \u2013 a comprehensive survey. Comput. Commun. 36(2), 121\u2013134 (2013)","journal-title":"Comput. Commun."},{"issue":"4","key":"9836_CR14","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algoritmica 20(4), 374\u2013387 (1998)","journal-title":"Algoritmica"},{"issue":"1","key":"9836_CR15","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s10898-005-8466-1","volume":"35","author":"M Min","year":"2006","unstructured":"Min, M., Du, H., Jia, X., Huang, C.X., Huang, S.C.H., Wu, W.: Improving construction for connected dominating set with steiner tree in wireless sensor networks. J. Glob. Optim. 35(1), 111\u2013119 (2006)","journal-title":"J. Glob. Optim."},{"key":"9836_CR16","doi-asserted-by":"crossref","unstructured":"Butenko, S., Cheng, X., Obviera, C.A., Pardalos, P.: A new heuristic for the minimum connected dominating set problem on ad-hoc wireless networks. In: Recent Developments in Cooperative Control and Optimization, pp. 61\u201373 (2004)","DOI":"10.1007\/978-1-4613-0219-3_4"},{"key":"9836_CR17","doi-asserted-by":"crossref","unstructured":"Alzoubi, K., Wan, R.-J., Frieder, O.: New distributed algorithm for connected dominating set in wireless ad-hoc networks. In: International Conference on System Sciences, pp. 3849\u20133855 (2002)","DOI":"10.1145\/513800.513820"},{"key":"9836_CR18","doi-asserted-by":"crossref","unstructured":"Alzoubi, K.M., Wan, R.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad-hoc networks. In: ACM International Symposium on Mobile Ad-Hoc Networking and Computing, pp. 157\u2013164 (2002)","DOI":"10.1145\/513819.513820"},{"key":"9836_CR19","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Dobrev, S., Fevens, T., Gonz\u00e1lez-Aguilar, H., Kranakis, E., Opatrny, J., Urrutia, J.: Local algorithms for dominating and connected dominating sets of unit disk graphs with location aware nodes. In: Latin American Symposium on Theoretical Informatics, vol. 4957, pp. 158\u2013169 (2008)","DOI":"10.1007\/978-3-540-78773-0_14"},{"issue":"3","key":"9836_CR20","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/1167935.1167941","volume":"2","author":"S Funke","year":"2006","unstructured":"Funke, S., Kesselman, A., Meyer, U., Segal, M.: A simple improved distributed algorithm for minimum CDS in unit disk graphs. ACM Transactions on Sensor Networks 2(3), 444\u2013453 (2006)","journal-title":"ACM Transactions on Sensor Networks"},{"issue":"l","key":"9836_CR21","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.adhoc.2008.01.003","volume":"7","author":"B Han","year":"2009","unstructured":"Han, B.: Zone-based virtual backbone formation in wireless ad-hoc networks. Ad Hoc Netw. 7(l), 183\u2013200 (2009)","journal-title":"Ad Hoc Netw."},{"key":"9836_CR22","doi-asserted-by":"crossref","unstructured":"Wu, J., Li, H.: On calculating connected dominating set for efficient routing in ad-hoc wireless networks. In: International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7\u201314 (1999)","DOI":"10.1145\/313239.313261"},{"key":"9836_CR23","doi-asserted-by":"crossref","unstructured":"Wu, J., Gao, M., Stojmenovic, I.: On calculating power-aware connected dominating sets for efficient routing in ad-hoc wireless networks. In: International Conference on Parallel Processing, pp. 346\u2013356 (2001)","DOI":"10.1109\/ICPP.2001.952080"},{"key":"9836_CR24","doi-asserted-by":"crossref","unstructured":"Kassaei, H., Mehrandish, M., Narayanan, L., Opatrny, J.: A new local algorithm for backbone formation in ad-hoc networks. In: ACM Symposium on Performance Evaluation of Wireless Ad-Hoc, Sensor, and Ubiquitous Networks, pp. 49\u201357 (2009)","DOI":"10.1145\/1641876.1641886"},{"key":"9836_CR25","doi-asserted-by":"crossref","unstructured":"Yu, J., Jia, L., Yu, D., Li, G., Cheng, X.: Minimum connected dominating set construction in wireless networks under the beeping model. In: Computer Communications (INFOCOM), pp. 972\u2013980 (2015)","DOI":"10.1109\/INFOCOM.2015.7218469"},{"key":"9836_CR26","doi-asserted-by":"crossref","unstructured":"Chaturvedi, O., Kaur, P., Ahuja, N., Prakash, T.: Improved algorithms for construction of connected dominating set in MANETs. In: Cloud System and Big Data Engineering (Confluence), pp. 559\u2013564 (2016)","DOI":"10.1109\/CONFLUENCE.2016.7508182"},{"key":"9836_CR27","unstructured":"Tang, W., Li, J., He, Q.: A highly efficient distributed algorithm for constructing CDS in wireless ad hoc networks with partial neighborhood notification. In: International Conference on Modelling and Simulation, pp. 549\u2013553 (2015)"},{"issue":"7","key":"9836_CR28","first-page":"721","volume":"6","author":"M Thai","year":"2007","unstructured":"Thai, M., Wang, F., Liu, D., Zhu, S., Du, D.: Connected dominating sets in wireless networks with different transmission ranges. Mob. Commun. 6(7), 721\u2013730 (2007)","journal-title":"Mob. Commun."},{"key":"9836_CR29","doi-asserted-by":"crossref","unstructured":"Raei, H., Fathi, M., Akhhlaghi, A., Ahmadipoor, B.: A new distributed algorithm for virtual backbone in wireless sensor networks with different transmission ranges. In: Computer Systems and Applications, pp. 983\u2013988 (2009)","DOI":"10.1109\/AICCSA.2009.5069451"},{"key":"9836_CR30","doi-asserted-by":"crossref","unstructured":"Raei, H., Sarram, M., Salimi, B., Adibnya, F.: Energy-aware distributed algorithm for virtual backbone in wireless sensor networks. In: Innovations in Information Technology, pp. 435\u2013439 (2008)","DOI":"10.1109\/INNOVATIONS.2008.4781762"},{"issue":"9","key":"9836_CR31","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1109\/TPDS.2002.1036062","volume":"13","author":"J Wu","year":"2002","unstructured":"Wu, J.: An extended dominating-set-based routing in ad hoc wireless networks with unidirectional links. IEEE Trans. Parallel Distrib. Syst. 13(9), 866\u2013881 (2002)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9836_CR32","doi-asserted-by":"crossref","unstructured":"Park, M.A., Willson, J., Wang, C., Thai, M., Wu, W., Farago, A.: A dominating and absorbent set in a wireless adhoc network with different transmission ranges. In: Mobile Ad hoc Networking and Computing, pp. 22\u201331 (2007)","DOI":"10.1145\/1288107.1288111"},{"key":"9836_CR33","doi-asserted-by":"crossref","unstructured":"Kassaei, H., Narayanan, L.: A new algorithm for backbone formation in ad hoc wireless networks of nodes with different transmission ranges. In: Wireless and Mobile Computing, pp. 83\u201390 (2010)","DOI":"10.1109\/WIMOB.2010.5644866"},{"issue":"2","key":"9836_CR34","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1504\/IJSNET.2015.071629","volume":"19","author":"Z Zhang","year":"2015","unstructured":"Zhang, Z., Wu, W., Wu, L., Li, Y., Chen, Z.: Strongly connected dominating and absorbing set in directed disk graph. International Journal of Sensor Networks 19(2), 69\u201377 (2015)","journal-title":"International Journal of Sensor Networks"},{"key":"9836_CR35","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1016\/j.tcs.2008.09.058","volume":"410","author":"D Li","year":"2009","unstructured":"Li, D., Duc, H., Wan, P.: Construction of strongly connected dominating sets in asymmetric multihop wireless networks. Theor. Comput. Sci. 410, 661\u2013669 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9836_CR36","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2), 153\u2013177 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"9836_CR37","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"9836_CR38","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/TMC.2007.1034","volume":"6","author":"M Thai","year":"2007","unstructured":"Thai, M., Wang, F., Liu, D., Zhu, S., Du, D.: Connected dominating sets in wireless networks with different transmission ranges. Mobile Computing 6(7), 721\u2013730 (2007)","journal-title":"Mobile Computing"},{"issue":"3","key":"9836_CR39","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1007\/s11276-014-0819-6","volume":"21","author":"N Ahn","year":"2015","unstructured":"Ahn, N., Park, S.: An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks. Wirel. Netw 21(3), 783\u2013792 (2015)","journal-title":"Wirel. Netw"},{"key":"9836_CR40","doi-asserted-by":"crossref","unstructured":"Tiwari, R., Thai, M.T.: On enhancing fault tolerance of virtual backbone in a wireless sensor network with unidirectional links sensors. In: Theory, Algorithms, and Applications, pp. 3\u201318 (2011)","DOI":"10.1007\/978-0-387-88619-0_1"},{"key":"9836_CR41","doi-asserted-by":"crossref","unstructured":"Tiwari, R., Mishra, T., Li, Y.: k-strongly connected dominating and absorbing set in wireless ad hoc networks with unidirectional links. In: Wireless Algorithm, Systems and Applications, pp. 103\u2013112 (2007)","DOI":"10.1109\/WASA.2007.25"},{"key":"9836_CR42","doi-asserted-by":"crossref","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. In: ACM Symposium on the Theory of Computation, pp. 100\u2013105 (2003)","DOI":"10.1145\/780555.780558"},{"issue":"2","key":"9836_CR43","first-page":"119","volume":"155","author":"I Caragiannisa","year":"2007","unstructured":"Caragiannisa, I., Fishkinb, A.V., Kaklamanisa, C., Papaioannoua, E.: Randomized online algorithms and lower bounds for computing large independent sets in disk graphs. Symposium on Mathematical Foundations of Computer Science 155 (2), 119\u2013136 (2007)","journal-title":"Symposium on Mathematical Foundations of Computer Science"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9836-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9836-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9836-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T17:15:18Z","timestamp":1751217318000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9836-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,10]]},"references-count":43,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["9836"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9836-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2018,1,10]]}}}