{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:55:11Z","timestamp":1743141311086,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319217406"},{"type":"electronic","value":"9783319217413"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21741-3_6","type":"book-chapter","created":{"date-parts":[[2015,8,3]],"date-time":"2015-08-03T12:21:28Z","timestamp":1438604488000},"page":"81-93","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The k-Observer Problem on d-regular Graphs"],"prefix":"10.1007","author":[{"given":"Benjamin","family":"Ries","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"Schamberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,4]]},"reference":[{"issue":"1\u20135","key":"6_CR1","first-page":"15","volume":"1","author":"HB Acharya","year":"2012","unstructured":"Acharya, H.B., Choi, T., Bazzi, R.A., Gouda, M.G.: The k-observer problem in computer networks Networking. Science 1(1\u20135), 15\u201322 (2012)","journal-title":"Science"},{"doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No Small Linear Program Approximates Vertex Cover within a Factor 2 - \n$$\\epsilon $$\n. ArXiv e-prints, March 2015","key":"6_CR2","DOI":"10.1109\/FOCS.2015.73"},{"issue":"13","key":"6_CR3","doi-asserted-by":"crossref","first-page":"1943","DOI":"10.1016\/j.dam.2013.02.024","volume":"161","author":"B Bre\u0161ar","year":"2013","unstructured":"Bre\u0161ar, B., Jakovac, M., Katreni\u010d, J., Semani\u0161in, G., Taranenko, A.: On the vertex k-path cover. Discrete Applied Mathematics 161(13), 1943\u20131949 (2013)","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.dam.2014.05.042","volume":"177","author":"B Bre\u0161ar","year":"2014","unstructured":"Bre\u0161ar, B., Krivo\u0161-Bellu\u0161, R., Semani\u0161in, G., \u0160parl, P.: On the weighted k-path vertex cover problem. Discrete Applied Mathematics 177, 14\u201318 (2014)","journal-title":"Discrete Applied Mathematics"},{"issue":"12","key":"6_CR5","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.dam.2011.04.008","volume":"159","author":"B Bre\u0161ar","year":"2011","unstructured":"Bre\u0161ar, B., Kardo\u0161, F., Katreni\u010d, J., Semani\u0161in, G.: Minimum k-path vertex cover. Discrete Applied Mathematics 159(12), 1189\u20131195 (2011)","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Boliac, R., Lozin, V.V.: On computing the dissociation number of bipartite graphs (2001)","key":"6_CR6"},{"issue":"6","key":"6_CR7","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1109\/35.587723","volume":"35","author":"KL Calvert","year":"1997","unstructured":"Calvert, K.L., Doar, M.B., Zegura, E.W.: Modeling internet topology. IEEE Communications Magazine 35(6), 160\u2013163 (1997)","journal-title":"IEEE Communications Magazine"},{"doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics, pp. 439\u2013485 (2005)","key":"6_CR8","DOI":"10.4007\/annals.2005.162.439"},{"unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996, pp. 310\u2013319. IEEE (1996)","key":"6_CR9"},{"unstructured":"Uriel, F.: Vertex cover is hardest to approximate on regular graphs. Technical report, Citeseer (2003)","key":"6_CR10"},{"doi-asserted-by":"crossref","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: ACM SIGCOMM Computer Communication Review, vol. 29, pp. 251\u2013262. ACM (1999)","key":"6_CR11","DOI":"10.1145\/316194.316229"},{"issue":"3","key":"6_CR12","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"S Dorit","year":"1983","unstructured":"Dorit, S.: Hochbaum. Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics 6(3), 243\u2013254 (1983)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- \n$$\\varepsilon $$\n. Journal of Computer and System Sciences 74(3), 335\u2013349 (2008)","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"Lynch, N.A.: Distributed algorithms. Morgan Kaufmann (1996)","key":"6_CR14"},{"key":"6_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/978-3-642-12368-9_8","volume-title":"Information Security Theory and Practices","author":"M Novotn\u00fd","year":"2010","unstructured":"Novotn\u00fd, M.: Design and analysis of a generalized canvas protocol. In: Samarati, P., Tunstall, M., Posegga, J., Markantonakis, K., Sauveron, D. (eds.) WISTP 2010. LNCS, vol. 6033, pp. 106\u2013121. Springer, Heidelberg (2010)"},{"doi-asserted-by":"crossref","unstructured":"Scott, A., Jeavons, P., Xu, L.: Feedback from nature: an optimal distributed algorithm for maximal independent set selection. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pp. 147\u2013156. ACM (2013)","key":"6_CR16","DOI":"10.1145\/2484239.2484247"},{"issue":"14","key":"6_CR17","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/j.ipl.2011.04.009","volume":"111","author":"T Jianhua","year":"2011","unstructured":"Jianhua, T., Zhou, W.: A factor 2 approximation algorithm for the vertex cover p3 problem. Information Processing Letters 111(14), 683\u2013686 (2011)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21741-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T14:09:20Z","timestamp":1675865360000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21741-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319217406","9783319217413"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21741-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"4 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}