{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:08:42Z","timestamp":1725574122267},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642176784"},{"type":"electronic","value":"9783642176791"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-17679-1_6","type":"book-chapter","created":{"date-parts":[[2011,1,5]],"date-time":"2011-01-05T18:44:30Z","timestamp":1294253070000},"page":"65-76","source":"Crossref","is-referenced-by-count":3,"title":["Deterministic Dominating Set Construction in Networks with Bounded Degree"],"prefix":"10.1007","author":[{"given":"Roy","family":"Friedman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Kogan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-642-04355-0_21","volume-title":"Distributed Computing","author":"M. \u00c5strand","year":"2009","unstructured":"\u00c5strand, M., Flor\u00e9en, P., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: A local 2-approximation algorithm for the vertex cover problem. In: DISC 2009. LNCS, vol.\u00a05805, pp. 191\u2013205. Springer, Heidelberg (2009)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Astrand, M., Suomela, J.: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In: Proc. 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 294\u2013302 (2010)","DOI":"10.1145\/1810479.1810533"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Chen, Y.P., Liestman, A.L.: Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In: Proc. ACM Int. Symp. on Mob. Ad Hoc Networking and Computing (MobiHoc), pp. 165\u2013172 (2002)","DOI":"10.1145\/513800.513821"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Chlebik, M., Chlebikova, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput.\u00a0206(11) (2008)","DOI":"10.1016\/j.ic.2008.07.003"},{"issue":"3","key":"6_CR5","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research\u00a04(3), 233\u2013235 (1979)","journal-title":"Mathematics of Operations Research"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-540-78773-0_14","volume-title":"LATIN 2008: Theoretical Informatics","author":"J. Czyzowicz","year":"2008","unstructured":"Czyzowicz, J., Dobrev, S., Fevens, T., Gonzalez-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: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 158\u2013169. Springer, Heidelberg (2008)"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: Proc. IEEE Int. Conf. on Comm (ICC), pp. 376\u2013380 (1997)","DOI":"10.1109\/ICC.1997.605303"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Dong, Q., Bejerano, Y.: Building robust nomadic wireless mesh networks using directional antennas. In: Proc. IEEE INFOCOM, pp. 1624\u20131632 (2008)","DOI":"10.1109\/INFOCOM.2008.223"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045, 314\u2013318 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"6_CR10","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1109\/MWC.2005.1404569","volume":"12","author":"E. Ferro","year":"2005","unstructured":"Ferro, E., Potorti, F.: Bluetooth and Wi-Fi wireless protocols: a survey and a comparison. IEEE Wireless Communications\u00a012(1), 12\u201326 (2005)","journal-title":"IEEE Wireless Communications"},{"key":"6_CR11","series-title":"LNCS","first-page":"159","volume-title":"OPODIS 2009","author":"R. Friedman","year":"2009","unstructured":"Friedman, R., Kogan, A.: Efficient power utilization in multi-radio wireless ad hoc networks. In: Abdelzaher, T., Raynal, M., Santoro, N. (eds.) OPODIS 2009. LNCS, vol.\u00a05923, pp. 159\u2013173. Springer, Heidelberg (2009)"},{"key":"6_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. Ltd., New York (1979)"},{"key":"6_CR13","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\u00a020, 374\u2013387 (1998)","journal-title":"Algorithmica"},{"issue":"6","key":"6_CR14","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1016\/j.jpdc.2007.03.001","volume":"67","author":"B. Han","year":"2007","unstructured":"Han, B., Jia, W.: Clustering wireless ad hoc networks with weakly connected dominating set. Journal of Parallel and Distr. Computing\u00a067(6), 727\u2013737 (2007)","journal-title":"Journal of Parallel and Distr. Computing"},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-540-27820-7_6","volume-title":"Algorithmic Aspects of Wireless Sensor Networks","author":"T. Herman","year":"2004","unstructured":"Herman, T., Tixeuil, S.: A distributed TDMA slot assignment algorithm for wireless sensor networks. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2004. LNCS, vol.\u00a03121, pp. 45\u201358. Springer, Heidelberg (2004)"},{"key":"6_CR16","unstructured":"Jia, L., Rajaraman, R., Suel, T.: An efficient distributed algorithm for constructing small dominating sets. In: Proc. ACM Symp. on Principles of Distr. Comp (PODC), pp. 33\u201342 (2001)"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-540-45172-3_9","volume-title":"Peer-to-Peer Systems II","author":"M.F. Kaashoek","year":"2003","unstructured":"Kaashoek, M.F., Karger, D.R.: Koorde: A simple degree-optimal distributed hash table. In: Kaashoek, M.F., Stoica, I. (eds.) IPTPS 2003. LNCS, vol.\u00a02735, pp. 98\u2013107. Springer, Heidelberg (2003)"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: Proc. Symp. on Paral. in Algorithms and Architectures (SPAA), pp. 138\u2013144 (2009)","DOI":"10.1145\/1583991.1584032"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proc. ACM Symp. on Principles of Distr. Comp. (PODC), pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: Proc. ACM Symp. on Principles of Distr. Comp (PODC), pp. 60\u201368 (2005)","DOI":"10.1145\/1073814.1073826"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 980\u2013989 (2006)","DOI":"10.1145\/1109557.1109666"},{"key":"6_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-540-87779-0_27","volume-title":"Distributed Computing","author":"C. Lenzen","year":"2008","unstructured":"Lenzen, C., Wattenhofer, R.: Leveraging linial\u2019s locality limit. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 394\u2013407. Springer, Heidelberg (2008)"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Liang, B., Haas, Z.J.: Virtual backbone generation and maintenance in ad hoc network mobility management. In: Proc. IEEE INFOCOM, pp. 1293\u20131302 (2000)","DOI":"10.1109\/INFCOM.2000.832522"},{"issue":"1","key":"6_CR24","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Malkhi, D., Naor, M., Ratajczak, D.: Viceroy: a scalable and dynamic emulation of the butterfly. In: Proc. ACM Symp. on Principles of Distr. Comp (PODC), pp. 183\u2013192 (2002)","DOI":"10.1145\/571825.571857"},{"issue":"2","key":"6_CR26","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/PL00008932","volume":"14","author":"A. Panconesi","year":"2001","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distributed Computing\u00a014(2), 97\u2013100 (2001)","journal-title":"Distributed Computing"},{"key":"6_CR27","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed computing: a locality-sensitive approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM, Philadelphia (2000)"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Rhee, I., Warrier, A., Min, J., Xu, L.: DRAND: distributed randomized TDMA scheduling for wireless ad-hoc networks. In: Proc. 7th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 190\u2013201 (2006)","DOI":"10.1145\/1132905.1132927"},{"issue":"2","key":"6_CR29","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1023\/A:1019045801829","volume":"1","author":"R. Sivakumar","year":"1998","unstructured":"Sivakumar, R., Das, B., Bharghavan, V.: Spine routing in ad hoc networks. Cluster Computing\u00a01(2), 237\u2013248 (1998)","journal-title":"Cluster Computing"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Wu, J., Dai, F., Gao, M., Stojmenovic, I.: On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. Journal of Communications and Networks, 59\u201370 (2002)","DOI":"10.1109\/JCN.2002.6596934"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing and Networking"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17679-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,23]],"date-time":"2019-03-23T10:54:32Z","timestamp":1553338472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17679-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642176784","9783642176791"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17679-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}