乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,28]],"date-time":"2024-03-28T04:39:39Z","timestamp":1711600779148},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T00:00:00Z","timestamp":1590192000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T00:00:00Z","timestamp":1590192000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,10]]},"abstract":"Abstract<\/jats:title>We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC)<\/jats:sc> 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.<\/jats:p>","DOI":"10.1007\/s00224-020-09981-w","type":"journal-article","created":{"date-parts":[[2020,5,23]],"date-time":"2020-05-23T15:02:27Z","timestamp":1590246147000},"page":"1158-1182","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Complexity of Min-Power Asymmetric Connectivity"],"prefix":"10.1007","volume":"64","author":[{"given":"Matthias","family":"Bentert","sequence":"first","affiliation":[]},{"given":"Roman","family":"Haag","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Hofer","sequence":"additional","affiliation":[]},{"given":"Tomohiro","family":"Koana","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,23]]},"reference":[{"key":"9981_CR1","doi-asserted-by":"crossref","unstructured":"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\u2013142. ACM (2006)","DOI":"10.1145\/1132905.1132921"},{"key":"9981_CR2","doi-asserted-by":"crossref","unstructured":"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 \u201917), volume 10718 of LNCS, pp. 26\u201340. Springer (2017)","DOI":"10.1007\/978-3-319-72751-6_3"},{"key":"9981_CR3","unstructured":"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)"},{"issue":"3","key":"9981_CR4","doi-asserted-by":"publisher","first-page":"1527","DOI":"10.1137\/100819540","volume":"27","author":"G C\u0103linescu","year":"2013","unstructured":"C\u0103linescu, G.: Approximate min-power strong connectivity. SIAM J. Discrete Math. 27(3), 1527\u20131543 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"9981_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s10878-014-9738-9","volume":"31","author":"G C\u0103linescu","year":"2016","unstructured":"C\u0103linescu, G.: 1.61-approximation for min-power strong connectivity with two power levels. J. Comb. Optim. 31(1), 239\u2013259 (2016)","journal-title":"J. Comb. Optim."},{"key":"9981_CR6","doi-asserted-by":"crossref","unstructured":"C\u0103linescu, 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 \u201903), volume 2832 of LNCS, pp. 114\u2013126. Springer (2003)","DOI":"10.1007\/978-3-540-39658-1_13"},{"issue":"2","key":"9981_CR7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00453-006-1230-1","volume":"47","author":"P Carmi","year":"2007","unstructured":"Carmi, P., Katz, M.J.: Power assignment in radio networks with two power levels. Algorithmica 47(2), 183\u2013201 (2007)","journal-title":"Algorithmica"},{"key":"9981_CR8","unstructured":"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\u201905), pp. 5. IEEE (2005)"},{"issue":"3","key":"9981_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1109\/26.20105","volume":"37","author":"W-T Chen","year":"1989","unstructured":"Chen, W.-T., Huang, N.-F.: The strongly connecting problem on multihop packet radio networks. IEEE Trans. Commun. 37(3), 293\u2013295 (1989)","journal-title":"IEEE Trans. Commun."},{"issue":"2","key":"9981_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1023\/B:MONE.0000013624.32948.87","volume":"9","author":"AEF Clementi","year":"2004","unstructured":"Clementi, A.E.F., Penna, P., Silvestri, R.: On the power assignment problem in radio networks. Mobile Netw. Appl. 9(2), 125\u2013140 (2004)","journal-title":"Mobile Netw. Appl."},{"key":"9981_CR11","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"4","key":"9981_CR12","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/s00224-011-9367-y","volume":"50","author":"MR Fellows","year":"2012","unstructured":"Fellows, M.R., Gaspers, S., Rosamond, F.A.: Parameterizing by the number of numbers. Theor. Comput. Syst. 50(4), 675\u2013693 (2012)","journal-title":"Theor. Comput. Syst."},{"issue":"2","key":"9981_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 21 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9981_CR14","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9981_CR15","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1504\/IJSNET.2009.023314","volume":"5","author":"R Iyengar","year":"2009","unstructured":"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\u201347 (2009)","journal-title":"Int. J. Sens. Netw."},{"key":"9981_CR16","unstructured":"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 \u201904), IEEE (2004)"},{"key":"9981_CR17","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2012.04.007","volume":"16","author":"M Sorge","year":"2012","unstructured":"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\u201333 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"9981_CR18","doi-asserted-by":"crossref","unstructured":"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\u2013474. CRC Press \/ Taylor & Francis (2005)","DOI":"10.1201\/9780203323687.ch28"}],"updated-by":[{"updated":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"DOI":"10.1007\/s00224-021-10057-6","type":"correction","label":"Correction"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09981-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09981-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09981-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T06:03:42Z","timestamp":1629180222000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09981-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,23]]},"references-count":18,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["9981"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09981-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,23]]},"assertion":[{"value":"23 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2021","order":2,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":4,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00224-021-10057-6","URL":"https:\/\/doi.org\/10.1007\/s00224-021-10057-6","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}