{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T11:27:57Z","timestamp":1771414077150,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,8,9]],"date-time":"2014-08-09T00:00:00Z","timestamp":1407542400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Wireless Netw"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s11276-014-0784-0","type":"journal-article","created":{"date-parts":[[2014,8,8]],"date-time":"2014-08-08T09:33:46Z","timestamp":1407490426000},"page":"281-295","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["An exact algorithm for maximum lifetime data gathering tree without aggregation in wireless sensor networks"],"prefix":"10.1007","volume":"21","author":[{"given":"Xiaojun","family":"Zhu","sequence":"first","affiliation":[]},{"given":"Xiaobing","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Guihai","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,8,9]]},"reference":[{"issue":"3","key":"784_CR1","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1287\/mnsc.34.3.331","volume":"34","author":"K Altinkemer","year":"1988","unstructured":"Altinkemer, K., & Gavish, B. (1988). Heuristics with constant error guarantees for the design of tree networks. Management Science, 34(3), 331\u2013341.","journal-title":"Management Science"},{"issue":"4","key":"784_CR2","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.disopt.2012.08.002","volume":"9","author":"EM Arkin","year":"2012","unstructured":"Arkin, E. M., Guttmann-Beck, N., & Hassin, R. (2012). The (k, k)-capacitated spanning tree problem. Discrete Optimization, 9(4), 258\u2013266.","journal-title":"Discrete Optimization"},{"key":"784_CR3","unstructured":"Berkelaar, M., Eikland, K., & Notebaert, P. (2010). lp_solve 5.5.2.0. http:\/\/lpsolve.sourceforge.net\/5.5\/ . Accessed 2014-3-2."},{"key":"784_CR4","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T. H., Stein, C., Rivest, R. L., & Leiserson, C. E. (2001). Introduction to algorithms (2nd ed.). New York: McGraw-Hill Higher Education.","edition":"2"},{"key":"784_CR5","volume-title":"Graph theory","author":"R Diestel","year":"2006","unstructured":"Diestel, R. (2006). Graph theory (3rd ed.). Berlin: Springer.","edition":"3"},{"issue":"3","key":"784_CR6","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1137\/0207024","volume":"7","author":"HN Gabow","year":"1978","unstructured":"Gabow, H. N., & Myers, E. W. (1978). Finding all spanning trees of directed and undirected graphs. SIAM Journal on Computing, 7(3), 280\u2013287.","journal-title":"SIAM Journal on Computing"},{"key":"784_CR7","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W. H. Freeman & Co."},{"issue":"1","key":"784_CR8","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/322358.322367","volume":"30","author":"MR Garey","year":"1983","unstructured":"Garey, M. R., & Johnson, D. S. (1983). Formulations and algorithms for the capacitated minimal directed tree problem. Journal of the ACM, 30(1), 118\u2013132. doi: 10.1145\/322358.322367 .","journal-title":"Journal of the ACM"},{"issue":"6","key":"784_CR9","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., & Tarjan, R. (1973). Algorithm 447: Efficient algorithms for graph manipulation. Communications of ACM, 16(6), 372\u2013378.","journal-title":"Communications of ACM"},{"key":"784_CR10","doi-asserted-by":"crossref","unstructured":"Intanagonwiwat, C., Govindan, R., & Estrin, D. (2000). Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of ACM MobiCom.","DOI":"10.1145\/345910.345920"},{"issue":"2","key":"784_CR11","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1145\/1103963.1103967","volume":"1","author":"R Jothi","year":"2005","unstructured":"Jothi, R., & Raghavachari, B. (2005). Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design. ACM Transations on Algorithms, 1(2), 265\u2013282.","journal-title":"ACM Transations on Algorithms"},{"key":"784_CR12","doi-asserted-by":"crossref","unstructured":"Kuo, T. W., & Tsai, M. J. (2012). On the construction of data aggregation tree with minimum energy cost in wireless sensor networks: Np-completeness and approximation algorithms. In Proceedings of IEEE INFOCOM.","DOI":"10.1109\/INFCOM.2012.6195659"},{"issue":"3","key":"784_CR13","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra, J. K., Shmoys, D. B., & Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46(3), 259\u2013271.","journal-title":"Mathematical Programming"},{"key":"784_CR14","doi-asserted-by":"crossref","unstructured":"Liang, J., Wang, J., Cao, J., Chen, J., & Lu, M. (2010). An efficient algorithm for constructing maximum lifetime tree for data gathering without aggregation in wireless sensor networks. In Proceedings of IEEE INFOCOM.","DOI":"10.1109\/INFCOM.2010.5462181"},{"key":"784_CR15","doi-asserted-by":"crossref","unstructured":"Luo, D., Zhu, X., Wu, X., & Chen, G. (2011). Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks. In Proceedings of IEEE INFOCOM.","DOI":"10.1109\/INFCOM.2011.5934947"},{"key":"784_CR16","unstructured":"Peng, Y., Li, Z., Qiao, D., & Zhang, W. (2013). I2c: A holistic approach to prolong the sensor network lifetime. In Proceedings of IEEE INFOCOM."},{"key":"784_CR17","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"RC Read","year":"1975","unstructured":"Read, R. C., & Tarjan, R. (1975). Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5, 237\u2013252.","journal-title":"Networks"},{"key":"784_CR18","doi-asserted-by":"crossref","unstructured":"Shan, M., Chen, G., Luo, D., Zhu, X., & Wu, X. (2014). Building optimal shortest path data aggregation trees in wireless sensor networks. ACM Transactions on Sensor Networks, 11(1). Article No. 11.","DOI":"10.1145\/2629662"},{"issue":"3","key":"784_CR19","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1137\/S0097539794270881","volume":"26","author":"A Shioura","year":"1997","unstructured":"Shioura, A., Tamura, A., & Uno, T. (1997). An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM Journal on Computing, 26(3), 678\u2013692.","journal-title":"SIAM Journal on Computing"},{"key":"784_CR20","unstructured":"Wikipedia Contributors. (2014). Linear programming. http:\/\/en.wikipedia.org\/wiki\/Linear_programming . Accessed 2014-3-2."},{"key":"784_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms (1st ed.). New York, NY: Cambridge University Press.","edition":"1"},{"issue":"5","key":"784_CR22","doi-asserted-by":"crossref","first-page":"1571","DOI":"10.1109\/TNET.2010.2045896","volume":"18","author":"Y Wu","year":"2010","unstructured":"Wu, Y., Mao, Z., Fahmy, S., & Shroff, N. (2010). Constructing maximum-lifetime data-gathering forests in sensor networks. IEEE\/ACM Transactions on Networking, 18(5), 1571\u20131584.","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"784_CR23","doi-asserted-by":"crossref","unstructured":"Xiang, L., Luo, J., & Rosenberg, C. (2013). Compressed data aggregation: Energy efficient and high fidelity data collection. IEEE\/ACM Transactions on Networking, 21(6),\u00a01722\u20131735.","DOI":"10.1109\/TNET.2012.2229716"}],"container-title":["Wireless Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11276-014-0784-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11276-014-0784-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11276-014-0784-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T14:11:21Z","timestamp":1565705481000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11276-014-0784-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,9]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["784"],"URL":"https:\/\/doi.org\/10.1007\/s11276-014-0784-0","relation":{},"ISSN":["1022-0038","1572-8196"],"issn-type":[{"value":"1022-0038","type":"print"},{"value":"1572-8196","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,9]]}}}