{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:11:19Z","timestamp":1725567079682},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_85","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:34:13Z","timestamp":1127828053000},"page":"839-848","source":"Crossref","is-referenced-by-count":4,"title":["Distributed Weighted Vertex Cover via Maximal Matchings"],"prefix":"10.1007","author":[{"given":"Fabrizio","family":"Grandoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"85_CR1","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms\u00a02, 198\u2013203 (1981)","journal-title":"Journal of Algorithms"},{"key":"85_CR2","volume-title":"Linear programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Linear programming. W.H. Freeman, New York (1983)"},{"key":"85_CR3","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to algorithms, 6th edn. MIT Press and McGraw-Hill Book Company (1992)"},{"key":"85_CR4","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freemann (1979)"},{"key":"85_CR5","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Greed is good: Approximating independent sets in sparse and bounded-degree graphs. In: ACM Symposium on the Theory of Computing, pp. pp. 439\u2013448, pp. 23\u201325 (1994)","DOI":"10.1145\/195058.195221"},{"issue":"5","key":"85_CR6","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E. Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM Journal on Computing\u00a031(5), 1608\u20131623 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"85_CR7","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895480100373121","volume":"15","author":"M. Ha\u0144\u0107kowiak","year":"2001","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. SIAM Journal on Discrete Mathematics\u00a015(1), 41\u201357 (2001)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"85_CR8","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00b0astad","year":"2001","unstructured":"H\u00b0astad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"key":"85_CR9","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover, and set packing problems. Discrete Applied Mathematics\u00a06, 243\u2013254 (1983)","journal-title":"Discrete Applied Mathematics"},{"key":"85_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A. Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters\u00a022, 77\u201380 (1986)","journal-title":"Information Processing Letters"},{"issue":"2","key":"85_CR11","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.1994.1036","volume":"17","author":"S. Khuller","year":"1994","unstructured":"Khuller, S., Vishkin, U., Young, N.: A primal-dual parallel approximation technique applied to weighted set and vertex cover. Journal of Algorithms\u00a017(2), 280\u2013289 (1994)","journal-title":"Journal of Algorithms"},{"key":"85_CR12","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica\u00a022, 115\u2013123 (1985)","journal-title":"Acta Informatica"},{"key":"85_CR13","doi-asserted-by":"crossref","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. DISTCOMP: Distributed Computing\u00a014 (2001)","DOI":"10.1007\/PL00008932"},{"key":"85_CR14","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximization and complexity classes. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_85","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T22:37:08Z","timestamp":1586471828000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_85"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11533719_85","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}