{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:46:23Z","timestamp":1725860783400},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319411675"},{"type":"electronic","value":"9783319411682"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-41168-2_14","type":"book-chapter","created":{"date-parts":[[2016,7,3]],"date-time":"2016-07-03T21:26:28Z","timestamp":1467581188000},"page":"162-172","source":"Crossref","is-referenced-by-count":0,"title":["Near-Optimal Dominating Sets via Random Sampling"],"prefix":"10.1007","author":[{"given":"Martin","family":"Neh\u00e9z","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,5]]},"reference":[{"key":"14_CR1","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: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing MobiHoc 2002, pp. 165\u2013172. ACM, New York (2002)","DOI":"10.1145\/513800.513821"},{"issue":"3","key":"14_CR2","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1080\/15427951.2005.10129105","volume":"2","author":"C Cooper","year":"2005","unstructured":"Cooper, C., Klasing, R., Zito, M.: Lower bounds and algorithms for dominating sets in web graphs. Internet Math. 2(3), 275\u2013300 (2005)","journal-title":"Internet Math."},{"key":"14_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"14_CR4","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, New York (1979)"},{"key":"14_CR5","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1016\/j.tcs.2014.10.021","volume":"562","author":"M Gast","year":"2015","unstructured":"Gast, M., Hauptmann, M., Karpinski, M.: Inapproximability of dominating set in power law graphs. Theor. Comput. Sci. 562, 436\u2013452 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR6","first-page":"557","volume-title":"Introduction to Optimization, Decision Support and Search Methodologies","author":"CP Gomes","year":"2005","unstructured":"Gomes, C.P., Williams, R.: Approximation algorithms. In: Burke, E., Kendall, G. (eds.) Introduction to Optimization, Decision Support and Search Methodologies, pp. 557\u2013585. Kluwer, Dordrecht (2005)"},{"key":"14_CR7","volume-title":"Fundamentals of Domination in Graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker Inc., New York (1998)"},{"issue":"1","key":"14_CR8","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1287\/opre.39.1.100","volume":"39","author":"JN Hooker","year":"1991","unstructured":"Hooker, J.N., Garfinkel, R.S., Chen, C.K.: Finite dominating sets for network location problems. Oper. Res. 39(1), 100\u2013118 (1991). http:\/\/www.jstor.org\/stable\/171492 . INFORMS","journal-title":"Oper. Res."},{"key":"14_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-27903-2","volume-title":"Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms","author":"J Hromkovi\u010d","year":"2005","unstructured":"Hromkovi\u010d, J.: Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms. Springer, Heidelberg (2005)"},{"key":"14_CR10","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0165-4896(88)90041-8","volume":"16","author":"L Kelleher","year":"1988","unstructured":"Kelleher, L., Cozzens, M.: Dominating sets in social network graphs. Math. Soc. Sci. 16, 267\u2013279 (1988)","journal-title":"Math. Soc. Sci."},{"key":"14_CR11","first-page":"1","volume-title":"Encyclopedia of Algorithms","author":"D Kratsch","year":"2008","unstructured":"Kratsch, D., Fomin, F.V., Grandoni, F.: Exact algorithms for dominating set. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp. 1\u20135. Springer, New York (2008)"},{"key":"14_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Nacher, J.C., Akutsu, T.: Analysis on critical nodes in controlling complex networks using dominating sets. In: Proceedings of the International Conference on Signal-Image Technology & Internet-Based Systems, pp. 649\u2013654. IEEE Computer Society Press (2013)","DOI":"10.1109\/SITIS.2013.106"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Neh\u00e9z, M., Bern\u00e1t, D., Klau\u010do, M.: Comparison of algorithms for near-optimal dominating sets computation in real-world networks. In: Proceedings of the 16th International Conference on Computer Systems and Technologies, pp. 199\u2013206. ACM, New York (2015)","DOI":"10.1145\/2812428.2812443"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-57899-4_36","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"SE Nikoletseas","year":"1994","unstructured":"Nikoletseas, S.E., Spirakis, P.G.: Near-optimal dominating sets in dense random graphs in polynomial expected time. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 1\u201310. Springer, Heidelberg (1994)"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing STOC 1997, pp. 475\u2013484. ACM, New York (1997)","DOI":"10.1145\/258533.258641"},{"issue":"17","key":"14_CR17","doi-asserted-by":"crossref","first-page":"2147","DOI":"10.1016\/j.dam.2011.07.001","volume":"159","author":"JMM Rooij van","year":"2011","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for dominating set. Discrete Appl. Math. 159(17), 2147\u20132164 (2011)","journal-title":"Discrete Appl. Math."},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Wang, H., Zheng, H., Browne, F., Wang, C.: Minimum dominating sets in cell cycle specific protein interaction network. In: Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine, pp. 25\u201330. IEEE Computer Society Press (2014)","DOI":"10.1109\/BIBM.2014.6999122"},{"issue":"9","key":"14_CR19","doi-asserted-by":"crossref","first-page":"7156","DOI":"10.1073\/pnas.1311231111","volume":"111","author":"S Wuchty","year":"2014","unstructured":"Wuchty, S.: Controllabilty in protein interaction networks. Proc. Natl. Acad. Sci. USA 111(9), 7156\u20137160 (2014)","journal-title":"Proc. Natl. Acad. Sci. USA"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41168-2_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T13:43:58Z","timestamp":1498311838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41168-2_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319411675","9783319411682"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41168-2_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}