{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:24Z","timestamp":1725460044246},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642380150"},{"type":"electronic","value":"9783642380167"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38016-7_8","type":"book-chapter","created":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T17:58:58Z","timestamp":1367344738000},"page":"82-92","source":"Crossref","is-referenced-by-count":1,"title":["Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs"],"prefix":"10.1007","author":[{"given":"Guilherme D.","family":"da Fonseca","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Celina M. H.","family":"de Figueiredo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vin\u00edcius G. P.","family":"de S\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raphael","family":"Machado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., Teng, S.-H.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In: Proc. 43rd Annual ACM Symp. on Theory of Computing (STOC), pp. 273\u2013282 (2011)","DOI":"10.1145\/1993636.1993674"},{"issue":"1-3","key":"8_CR2","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics\u00a086(1-3), 165\u2013177 (1990)","journal-title":"Discrete Mathematics"},{"key":"8_CR3","unstructured":"De, M., Das, G., Nandy, S.: Approximation algorithms for the discrete piercing set problem for unit disk. In: Proc. 23rd Canadian Conference on Computational Geometry (CCCG), pp. 375\u2013380 (2011)"},{"key":"8_CR4","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer (2010)"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-12450-1_13","volume-title":"Approximation and Online Algorithms","author":"T. Erlebach","year":"2010","unstructured":"Erlebach, T., Mihal\u00e1k, M.: A (4 + \u03b5)-approximation for the minimum-weight dominating set problem in unit disk graphs. In: Bampis, E., Jansen, K. (eds.) WAOA 2009. LNCS, vol.\u00a05893, pp. 135\u2013146. Springer, Heidelberg (2010)"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Fejes T\u00f3th, L.: Lagerungen in der Ebene, auf der Kugel und im Raum. Springer (1953)","DOI":"10.1007\/978-3-662-01206-2"},{"issue":"2","key":"8_CR7","first-page":"431","volume":"44","author":"F. Fodor","year":"2003","unstructured":"Fodor, F.: The densest packing of 13 congruent circles in a circle. Contributions to Algebra and Geometry\u00a044(2), 431\u2013440 (2003)","journal-title":"Contributions to Algebra and Geometry"},{"key":"8_CR8","unstructured":"Frinch, S.R.: Mathematical Constants. Encyclopedia of Mathematics and its Applications, vol.\u00a094. Cambridge (2003)"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-15775-2_21","volume-title":"Algorithms \u2013 ESA 2010","author":"M. Gibson","year":"2010","unstructured":"Gibson, M., Pirwani, I.A.: Algorithms for dominating set in disk graphs: Breaking the logn barrier. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 243\u2013254. Springer, Heidelberg (2010)"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms\u00a026, 238\u2013274 (1998)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"8_CR11","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.ipl.2008.09.021","volume":"109","author":"J.L. Hurink","year":"2008","unstructured":"Hurink, J.L., Nieberg, T.: Approximating minimum independent dominating sets in wireless networks. Information Processing Letters\u00a0109(2), 155\u2013160 (2008)","journal-title":"Information Processing Letters"},{"issue":"2","key":"8_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks\u00a025(2), 59\u201368 (1995)","journal-title":"Networks"},{"key":"8_CR13","unstructured":"McDiarmid, C., Muller, T.: Integer realizations of disk and segment graphs. preprint, arXiv:1111.2931 (2011)"},{"key":"8_CR14","unstructured":"Nieberg, T.: Independent and Dominating Sets in Wireless Communication Graphs. PhD thesis, University of Twente (2006)"},{"issue":"4","key":"8_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1383369.1383380","volume":"4","author":"T. Nieberg","year":"2008","unstructured":"Nieberg, T., Hurink, J., Kern, W.: Approximation schemes for wireless networks. ACM Transactions on Algorithms\u00a04(4), 49:1\u201349:17 (2008)","journal-title":"ACM Transactions on Algorithms"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF01458387","volume":"83","author":"J. P\u00e1l","year":"1921","unstructured":"P\u00e1l, J.: Ein minimumprobleme f\u00fcr ovale. Math. Annalen\u00a083, 311\u2013319 (1921)","journal-title":"Math. Annalen"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Spinrad, J.: Efficient Graph Representations. Fields Inst. monographs. AMS (2003)","DOI":"10.1090\/fim\/019"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1077464.1077472","volume":"1","author":"D.E.D. Vinkemeier","year":"2005","unstructured":"Vinkemeier, D.E.D., Hougardy, S.: A linear-time approximation algorithm for weighted matchings in graphs. ACM Transactions on Algorithms\u00a01, 107\u2013122 (2005)","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"8_CR19","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.tcs.2009.06.022","volume":"412","author":"F. Zou","year":"2011","unstructured":"Zou, F., Wang, Y., Xu, X.-H., Li, X., Du, H., Wan, P., Wu, W.: New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theoretical Computer Science\u00a0412(3), 198\u2013208 (2011)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38016-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T15:11:00Z","timestamp":1557673860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38016-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642380150","9783642380167"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38016-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}