{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:38:59Z","timestamp":1782970739175,"version":"3.54.5"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,11]]},"abstract":"\n In this article, we consider the problem of computing a minimum-weight vertex-cover in an\n n<\/jats:italic>\n -node, weighted, undirected graph\n G<\/jats:italic>\n = (\n V<\/jats:italic>\n ,\n E<\/jats:italic>\n ). We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. Our algorithm runs in an expected number of\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n + log\n \u0174<\/jats:italic>\n ) communication rounds, where\n \u0174<\/jats:italic>\n is the average vertex-weight. The previous best algorithm for this problem requires\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n (log\n n<\/jats:italic>\n + log\n \u0174<\/jats:italic>\n )) rounds and it is not fully distributed.\n <\/jats:p>\n \n For a maximal matching\n M<\/jats:italic>\n in\n G<\/jats:italic>\n , it is a well-known fact that any vertex-cover in\n G<\/jats:italic>\n needs to have at least |\n M<\/jats:italic>\n | vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting.\n <\/jats:p>","DOI":"10.1145\/1435375.1435381","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T15:32:31Z","timestamp":1228923151000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Distributed weighted vertex cover via maximal matchings"],"prefix":"10.1145","volume":"5","author":[{"given":"Fabrizio","family":"Grandoni","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma Tor Vergata, Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[{"name":"Sapienza Universit\u00e0 di Roma, Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"e_1_2_1_2_1","volume-title":"Linear Programming","author":"Chv\u00e1tal V.","unstructured":"Chv\u00e1tal , V. 1983. Linear Programming . Freeman . Chv\u00e1tal, V. 1983. Linear Programming. Freeman."},{"key":"e_1_2_1_3_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1992. Introduction to Algorithms 6th ed. MIT Press and McGraw-Hill Book Company Cambridge MA. Cormen T. H. Leiserson C. E. and Rivest R. L. 1992. Introduction to Algorithms 6th ed. MIT Press and McGraw-Hill Book Company Cambridge MA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509915"},{"key":"e_1_2_1_5_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman. Garey M. R. and Johnson D. S. 1979. Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700381097"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100373121"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_84"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1036"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00290149"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1435375.1435381","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1435375.1435381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:16Z","timestamp":1750278136000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1435375.1435381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["10.1145\/1435375.1435381"],"URL":"https:\/\/doi.org\/10.1145\/1435375.1435381","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,11]]},"assertion":[{"value":"2006-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}