{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:35Z","timestamp":1750221095407,"version":"3.41.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T00:00:00Z","timestamp":1548374400000},"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":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2019,1,25]]},"abstract":"<jats:p>Computing the size of maximum independent sets is an NPhard problem for fixed graphs. Characterizing and designing efficient algorithms to compute (or approximate) this independence number for random graphs are notoriously difficult and still largely open issues. In this paper, we show that a low complexity degree-greedy exploration is actually asymptotically optimal on a large class of sparse random graphs. Encouraged by this result, we present and study two variants of sequential exploration algorithms: static and dynamic degree-aware explorations. We derive hydrodynamic limits for both of them, which in turn allow us to compute the size of the resulting independent set. Whereas the former is simpler to compute, the latter may be used to arbitrarily approximate the degree-greedy algorithm. Both can be implemented in a distributed manner. The corresponding hydrodynamic limits constitute an efficient method to compute or bound the independence number for a large class of sparse random graphs. As an application, we then show how our method may be used to compute (or approximate) the capacity of a large 802.11-based wireless network.<\/jats:p>","DOI":"10.1145\/3308897.3308910","type":"journal-article","created":{"date-parts":[[2019,1,28]],"date-time":"2019-01-28T14:01:39Z","timestamp":1548684099000},"page":"27-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Degree-Greedy Algorithms on Large Random Graphs"],"prefix":"10.1145","volume":"46","author":[{"given":"Paola","family":"Bermolen","sequence":"first","affiliation":[{"name":"Facultad de Ingenier\u00b4a, Universidad de la Rep\u00b4ublica, Montevideo, Uruguay"}]},{"given":"Matthieu","family":"Jonckheere","sequence":"additional","affiliation":[{"name":"Instituto de C\u00b4 alculo, Universidad de Buenos Aires and Conicet, Buenos Aires, Argentina"}]},{"given":"Federico","family":"Larroca","sequence":"additional","affiliation":[{"name":"Facultad de Ingenier\u00b4a, Universidad de la Rep\u00b4ublica, Montevideo, Uruguay"}]},{"given":"Manuel","family":"Saenz","sequence":"additional","affiliation":[{"name":"Instituto de C\u00b4 alculo, Universidad de Buenos Aires, Buenos Aires, Argentina"}]}],"member":"320","published-online":{"date-parts":[[2019,1,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Maximum matchings in sparse random graphs: Karp{Sipser revisited. Random Structures & Algorithms 12, 2","author":"Aronson Jonathan","year":"1998","unstructured":"Jonathan Aronson , Alan Frieze , and Boris G Pittel . 1998. Maximum matchings in sparse random graphs: Karp{Sipser revisited. Random Structures & Algorithms 12, 2 ( 1998 ), 111{177. Jonathan Aronson, Alan Frieze, and Boris G Pittel. 1998. Maximum matchings in sparse random graphs: Karp{Sipser revisited. Random Structures & Algorithms 12, 2 (1998), 111{177."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"P. Bermolen M. Jonckheere and P. Moyal. 2017. The jamming constant of uniform random graphs. Stochastic Processes and their Applications 127 7 (2017) 2138{2178.  P. Bermolen M. Jonckheere and P. Moyal. 2017. The jamming constant of uniform random graphs. Stochastic Processes and their Applications 127 7 (2017) 2138{2178.","DOI":"10.1016\/j.spa.2016.10.005"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.840210"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20716"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11511-017-0145-9"},{"key":"e_1_2_1_6_1","volume-title":"Asymptotic optimality of degree-greedy discovering of independent sets in Con guration Model graphs. arXiv preprint arXiv:1808.10358","author":"Jonckheere Matthieu","year":"2018","unstructured":"Matthieu Jonckheere and Manuel S aenz. 2018. Asymptotic optimality of degree-greedy discovering of independent sets in Con guration Model graphs. arXiv preprint arXiv:1808.10358 ( 2018 ). Matthieu Jonckheere and Manuel S aenz. 2018. Asymptotic optimality of degree-greedy discovering of independent sets in Con guration Model graphs. arXiv preprint arXiv:1808.10358 (2018)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.21"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2415465"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2010.89"},{"key":"e_1_2_1_10_1","volume-title":"A note on the Glauber dynamics for sampling independent sets. The electronic journal of combinatorics 8, 1","author":"Vigoda E.","year":"2001","unstructured":"E. Vigoda . 2001. A note on the Glauber dynamics for sampling independent sets. The electronic journal of combinatorics 8, 1 ( 2001 ). E. Vigoda. 2001. A note on the Glauber dynamics for sampling independent sets. The electronic journal of combinatorics 8, 1 (2001)."},{"key":"e_1_2_1_11_1","volume-title":"Di erential equations for random processes and random graphs. The annals of applied probability","author":"Wormald N. C.","year":"1995","unstructured":"N. C. Wormald . 1995. Di erential equations for random processes and random graphs. The annals of applied probability ( 1995 ), 1217{1235. N. C. Wormald. 1995. Di erential equations for random processes and random graphs. The annals of applied probability (1995), 1217{1235."}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3308897.3308910","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3308897.3308910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:58:03Z","timestamp":1750208283000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3308897.3308910"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,25]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1,25]]}},"alternative-id":["10.1145\/3308897.3308910"],"URL":"https:\/\/doi.org\/10.1145\/3308897.3308910","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2019,1,25]]},"assertion":[{"value":"2019-01-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}