Randomized greedy matching. II

We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that t...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 1995-01, Vol.6 (1), p.55-73
Main Authors: Aronson, Jonathan, Dyer, Martin, Frieze, Alan, Suen, Stephen
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c3087-4375f9674102e311e54862b22d8786e08a9241a318365c5223524f0b75056de43
cites cdi_FETCH-LOGICAL-c3087-4375f9674102e311e54862b22d8786e08a9241a318365c5223524f0b75056de43
container_end_page 73
container_issue 1
container_start_page 55
container_title Random structures & algorithms
container_volume 6
creator Aronson, Jonathan
Dyer, Martin
Frieze, Alan
Suen, Stephen
description We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ϵ such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ϵ. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs.
doi_str_mv 10.1002/rsa.3240060107
format article
fullrecord <record><control><sourceid>istex_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1002_rsa_3240060107</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>ark_67375_WNG_F25C1T6V_9</sourcerecordid><originalsourceid>FETCH-LOGICAL-c3087-4375f9674102e311e54862b22d8786e08a9241a318365c5223524f0b75056de43</originalsourceid><addsrcrecordid>eNqFj01Lw0AURQdRsFa3LiV_IPHNm-9lKbYNFIVadTlMk0mNNq3MFDT-elMiiitX7y7eudxDyCWFjALgdYguY8gBJFBQR2RAwegUOdXHh8wxNZrhKTmL8QUAFEM2IFcLty13Tf3py2QdvC_bpHH74rnerrMkz8_JSeU20V983yF5mNwsx7N0fjfNx6N5WjDQKuVMicpIxSmgZ5R6wbXEFWKplZYetDPdDseoZlIUApEJ5BWslAAhS8_ZkGR9bxF2MQZf2bdQNy60loI92NnOzv7adYDpgfd649t_vu3ifvSHTXu2jnv_8cO68Gql6kzs0-3UTlCM6VI-WsO-AL5vXi8</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Randomized greedy matching. II</title><source>Wiley Online Library Mathematics Backfiles</source><creator>Aronson, Jonathan ; Dyer, Martin ; Frieze, Alan ; Suen, Stephen</creator><creatorcontrib>Aronson, Jonathan ; Dyer, Martin ; Frieze, Alan ; Suen, Stephen</creatorcontrib><description>We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ϵ such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ϵ. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs.</description><identifier>ISSN: 1042-9832</identifier><identifier>EISSN: 1098-2418</identifier><identifier>DOI: 10.1002/rsa.3240060107</identifier><language>eng</language><publisher>New York: Wiley Subscription Services, Inc., A Wiley Company</publisher><ispartof>Random structures &amp; algorithms, 1995-01, Vol.6 (1), p.55-73</ispartof><rights>Copyright © 1995 Wiley Periodicals, Inc., A Wiley Company</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c3087-4375f9674102e311e54862b22d8786e08a9241a318365c5223524f0b75056de43</citedby><cites>FETCH-LOGICAL-c3087-4375f9674102e311e54862b22d8786e08a9241a318365c5223524f0b75056de43</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://onlinelibrary.wiley.com/doi/pdf/10.1002%2Frsa.3240060107$$EPDF$$P50$$Gwiley$$H</linktopdf><linktohtml>$$Uhttps://onlinelibrary.wiley.com/doi/full/10.1002%2Frsa.3240060107$$EHTML$$P50$$Gwiley$$H</linktohtml><link.rule.ids>314,776,780,27901,27902,50834,50943</link.rule.ids></links><search><creatorcontrib>Aronson, Jonathan</creatorcontrib><creatorcontrib>Dyer, Martin</creatorcontrib><creatorcontrib>Frieze, Alan</creatorcontrib><creatorcontrib>Suen, Stephen</creatorcontrib><title>Randomized greedy matching. II</title><title>Random structures &amp; algorithms</title><addtitle>Random Struct. Alg</addtitle><description>We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ϵ such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ϵ. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs.</description><issn>1042-9832</issn><issn>1098-2418</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1995</creationdate><recordtype>article</recordtype><recordid>eNqFj01Lw0AURQdRsFa3LiV_IPHNm-9lKbYNFIVadTlMk0mNNq3MFDT-elMiiitX7y7eudxDyCWFjALgdYguY8gBJFBQR2RAwegUOdXHh8wxNZrhKTmL8QUAFEM2IFcLty13Tf3py2QdvC_bpHH74rnerrMkz8_JSeU20V983yF5mNwsx7N0fjfNx6N5WjDQKuVMicpIxSmgZ5R6wbXEFWKplZYetDPdDseoZlIUApEJ5BWslAAhS8_ZkGR9bxF2MQZf2bdQNy60loI92NnOzv7adYDpgfd649t_vu3ifvSHTXu2jnv_8cO68Gql6kzs0-3UTlCM6VI-WsO-AL5vXi8</recordid><startdate>199501</startdate><enddate>199501</enddate><creator>Aronson, Jonathan</creator><creator>Dyer, Martin</creator><creator>Frieze, Alan</creator><creator>Suen, Stephen</creator><general>Wiley Subscription Services, Inc., A Wiley Company</general><scope>BSCLL</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>199501</creationdate><title>Randomized greedy matching. II</title><author>Aronson, Jonathan ; Dyer, Martin ; Frieze, Alan ; Suen, Stephen</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c3087-4375f9674102e311e54862b22d8786e08a9241a318365c5223524f0b75056de43</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1995</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Aronson, Jonathan</creatorcontrib><creatorcontrib>Dyer, Martin</creatorcontrib><creatorcontrib>Frieze, Alan</creatorcontrib><creatorcontrib>Suen, Stephen</creatorcontrib><collection>Istex</collection><collection>CrossRef</collection><jtitle>Random structures &amp; algorithms</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Aronson, Jonathan</au><au>Dyer, Martin</au><au>Frieze, Alan</au><au>Suen, Stephen</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Randomized greedy matching. II</atitle><jtitle>Random structures &amp; algorithms</jtitle><addtitle>Random Struct. Alg</addtitle><date>1995-01</date><risdate>1995</risdate><volume>6</volume><issue>1</issue><spage>55</spage><epage>73</epage><pages>55-73</pages><issn>1042-9832</issn><eissn>1098-2418</eissn><abstract>We consider the following randomized algorithm for finding a matching M in an arbitrary graph G = (V, E). Repeatedly, choose a random vertex u, then a random neighbour v of u. Add edge {u, v} to M and delete vertices u, v from G along with any vertices that become isolated. Our main result is that there exists a positive constant ϵ such that the expected ratio of the size of the matching produced to the size of largest matching in G is at least 0.5 + ϵ. We obtain stronger results for sparse graphs and trees and consider extensions to hypergraphs.</abstract><cop>New York</cop><pub>Wiley Subscription Services, Inc., A Wiley Company</pub><doi>10.1002/rsa.3240060107</doi><tpages>19</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1042-9832
ispartof Random structures & algorithms, 1995-01, Vol.6 (1), p.55-73
issn 1042-9832
1098-2418
language eng
recordid cdi_crossref_primary_10_1002_rsa_3240060107
source Wiley Online Library Mathematics Backfiles
title Randomized greedy matching. II
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-07T08%3A05%3A43IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-istex_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Randomized%20greedy%20matching.%20II&rft.jtitle=Random%20structures%20&%20algorithms&rft.au=Aronson,%20Jonathan&rft.date=1995-01&rft.volume=6&rft.issue=1&rft.spage=55&rft.epage=73&rft.pages=55-73&rft.issn=1042-9832&rft.eissn=1098-2418&rft_id=info:doi/10.1002/rsa.3240060107&rft_dat=%3Cistex_cross%3Eark_67375_WNG_F25C1T6V_9%3C/istex_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c3087-4375f9674102e311e54862b22d8786e08a9241a318365c5223524f0b75056de43%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true