{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T20:26:57Z","timestamp":1771705617195,"version":"3.50.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T00:00:00Z","timestamp":1551052800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T00:00:00Z","timestamp":1551052800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1217890"],"award-info":[{"award-number":["1217890"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1655073"],"award-info":[{"award-number":["1655073"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-019-00545-0","type":"journal-article","created":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T06:17:49Z","timestamp":1551075469000},"page":"2592-2605","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm"],"prefix":"10.1007","volume":"81","author":[{"given":"Samir","family":"Khuller","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5884-4893","authenticated-orcid":false,"given":"Sheng","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,25]]},"reference":[{"key":"545_CR1","doi-asserted-by":"crossref","unstructured":"Avrachenkov, K., Basu, P., Neglia, G., Ribeiro, B., Towsley, D.: Pay few, influence most: online myopic network covering. In: 2014 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 813\u2013818. IEEE (2014)","DOI":"10.1109\/INFCOMW.2014.6849335"},{"key":"545_CR2","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-35311-6_30","volume-title":"Internet and Network Economics","author":"C Borgs","year":"2012","unstructured":"Borgs, C., Brautbar, M., Chayes, J., Khanna, S., Lucier, B.: The power of local information in social networks. In: Leonardi, S. (ed.) Internet and Network Economics, pp. 406\u2013419. Springer, Berlin (2012)"},{"key":"545_CR3","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"key":"545_CR4","volume-title":"Connected Dominating Set: Theory and Applications","author":"D-Z Du","year":"2012","unstructured":"Du, D.-Z., Wan, P.-J.: Connected Dominating Set: Theory and Applications, vol. 77. Springer, New York (2012)"},{"key":"545_CR5","unstructured":"Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 717\u2013724. SIAM (2003)"},{"issue":"4","key":"545_CR6","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"545_CR7","doi-asserted-by":"publisher","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. Algorithmica 20(4), 374\u2013387 (1998)","journal-title":"Algorithmica"},{"issue":"1","key":"545_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1006\/inco.1998.2754","volume":"150","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf. Comput. 150(1), 57\u201374 (1999)","journal-title":"Inf. Comput."},{"key":"545_CR9","doi-asserted-by":"crossref","unstructured":"Khuller, S., Purohit, M., Sarpatwar, K.K.: Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1702\u20131713. SIAM (2014)","DOI":"10.1137\/1.9781611973402.123"},{"key":"545_CR10","unstructured":"Liu, Y., Liang, W.: Approximate coverage in wireless sensor networks. In: IEEE Conference on Local Computer Networks, 2005. 30th Anniversary, pp. 68\u201375. IEEE (2005)"},{"key":"545_CR11","unstructured":"Singla, A., Horvitz, E., Kohli, P., White, R., Krause, A.: Information gathering in networks via active exploration. In: Proceedings of the 24th International Conference on Artificial Intelligence, pp. 981\u2013988. AAAI Press (2015)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00545-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00545-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00545-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:33:25Z","timestamp":1589697205000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00545-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,25]]},"references-count":11,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["545"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00545-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,25]]},"assertion":[{"value":"11 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}