{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:39:00Z","timestamp":1782970740939,"version":"3.54.5"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2013,9,17]],"date-time":"2013-09-17T00:00:00Z","timestamp":1379376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2014,12]]},"DOI":"10.1007\/s00446-013-0194-z","type":"journal-article","created":{"date-parts":[[2013,9,16]],"date-time":"2013-09-16T09:09:21Z","timestamp":1379322561000},"page":"435-443","source":"Crossref","is-referenced-by-count":5,"title":["No sublogarithmic-time approximation scheme for bipartite vertex cover"],"prefix":"10.1007","volume":"27","author":[{"given":"Mika","family":"G\u00f6\u00f6s","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,9,17]]},"reference":[{"key":"194_CR1","unstructured":"\u00c5strand, M., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: Local algorithms in (weakly) coloured graphs (2010). Manuscript, arXiv:1002.0125 [cs.DC]"},{"key":"194_CR2","doi-asserted-by":"crossref","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Proc. 22nd Symposium on Distributed Computing (DISC 2008), LNCS, vol. 5218, pp. 78\u201392. Springer, Berlin (2008). doi: 10.1007\/978-3-540-87779-0_6","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"194_CR3","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005). http:\/\/diestel-graph-theory.com\/"},{"key":"194_CR4","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. In: Proc. 31st Symposium on Principles of Distributed Computing (PODC 2012), pp. 175\u2013184. ACM Press, New York (2012). doi: 10.1145\/2332432.2332465","DOI":"10.1145\/2332432.2332465"},{"key":"194_CR5","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: No sublogarithmic-time approximation scheme for bipartite vertex cover. In: Proc. 26th Symposium on Distributed Computing (DISC 2012), LNCS, vol. 7611, pp. 181\u2013194. Springer, Berlin (2012). doi: 10.1007\/978-3-642-33651-5_13","DOI":"10.1007\/978-3-642-33651-5_13"},{"key":"194_CR6","doi-asserted-by":"crossref","unstructured":"Hassidim, A., Kelner, J.A., Nguyen, H.N., Onak, K.: Local graph partitions for approximation and testing. In: Proc. 50th Symposium on Foundations of Computer Science (FOCS 2009), pp. 22\u201331. IEEE Computer Society Press, Los Alamitos (2009). doi: 10.1109\/FOCS.2009.77","DOI":"10.1109\/FOCS.2009.77"},{"issue":"4","key":"194_CR7","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439\u2013561 (2006). doi: 10.1090\/S0273-0979-06-01126-8","journal-title":"Bull. Am. Math. Soc."},{"issue":"3","key":"194_CR8","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1002\/rsa.20008","volume":"24","author":"S Janson","year":"2004","unstructured":"Janson, S.: Large deviations for sums of partly dependent random variables. Random Struct. Algor. 24(3), 234\u2013248 (2004). doi: 10.1002\/rsa.v24:3","journal-title":"Random Struct. Algor."},{"key":"194_CR9","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proc. 23rd Symposium on Principles of Distributed Computing (PODC 2004), pp. 300\u2013309. ACM Press, New York (2004). doi: 10.1145\/1011767.1011811","DOI":"10.1145\/1011767.1011811"},{"key":"194_CR10","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. 17th Symposium on Discrete Algorithms (SODA 2006), pp. 980\u2013989. ACM Press, New York (2006). doi: 10.1145\/1109557.1109666","DOI":"10.1145\/1109557.1109666"},{"key":"194_CR11","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: Lower and upper bounds (2010). Manuscript, arXiv:1011.5470 [cs.DC]"},{"key":"194_CR12","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Leveraging Linial\u2019s locality limit. In: Proc. 22nd Symposium on Distributed Computing (DISC 2008), LNCS, vol. 5218, pp. 394\u2013407. Springer, Berlin (2008). doi: 10.1007\/978-3-540-87779-0_27","DOI":"10.1007\/978-3-540-87779-0_27"},{"issue":"1","key":"194_CR13","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992). doi: 10.1137\/0221015","journal-title":"SIAM J. Comput."},{"key":"194_CR14","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/BF01303516","volume":"13","author":"N Linial","year":"1993","unstructured":"Linial, N., Saks, M.: Low diameter graph decompositions. Combinatorica 13, 441\u2013454 (1993). doi: 10.1007\/BF01303516","journal-title":"Combinatorica"},{"issue":"1","key":"194_CR15","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1006\/jctb.1994.1054","volume":"62","author":"M Morgenstern","year":"1994","unstructured":"Morgenstern, M.: Existence and explicit constructions of $$q + 1$$ q + 1 regular Ramanujan graphs for every prime power $$q$$ q . J. Comb. Theory Ser. B 62(1), 44\u201362 (1994). doi: 10.1006\/jctb.1994.1054","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"194_CR16","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995). doi: 10.1137\/S0097539793254571","journal-title":"SIAM J. Comput."},{"key":"194_CR17","doi-asserted-by":"crossref","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: Proc. 49th Symposium on Foundations of Computer Science (FOCS 2008), pp. 327\u2013336. IEEE Computer Society Press, Los Alamitos (2008). doi: 10.1109\/FOCS.2008.81","DOI":"10.1109\/FOCS.2008.81"},{"key":"194_CR18","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1998","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, Mineola (1998)"},{"issue":"1\u20133","key":"194_CR19","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.tcs.2007.04.040","volume":"381","author":"M Parnas","year":"2007","unstructured":"Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theor. Comput. Sci. 381(1\u20133), 183\u2013196 (2007). doi: 10.1016\/j.tcs.2007.04.040","journal-title":"Theor. Comput. Sci."},{"key":"194_CR20","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"194_CR21","doi-asserted-by":"crossref","unstructured":"Suomela, J.: Survey of local algorithms. ACM Comput. Surv. 45(2), 24:1\u201340 (2013). doi: 10.1145\/2431211.2431223 . http:\/\/www.cs.helsinki.fi\/local-survey\/","DOI":"10.1145\/2431211.2431223"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0194-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-013-0194-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-013-0194-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T03:56:03Z","timestamp":1563940563000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-013-0194-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,17]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["194"],"URL":"https:\/\/doi.org\/10.1007\/s00446-013-0194-z","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,17]]}}}