Degree-greedy algorithms on large random graphs
Computing the size of maximum independent sets is an NP-hard 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 c...
Guardado en:
| Publicado: |
2019
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01635999_v46_n3_p27_Bermolen http://hdl.handle.net/20.500.12110/paper_01635999_v46_n3_p27_Bermolen |
| Aporte de: |
| id |
paper:paper_01635999_v46_n3_p27_Bermolen |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_01635999_v46_n3_p27_Bermolen2023-06-08T15:14:22Z Degree-greedy algorithms on large random graphs Exploration algorithms Independence number Large random graphs Computational complexity Graphic methods Hydrodynamics IEEE Standards 802.11-based wireless networks Asymptotically optimal Degree-greedy algorithm Exploration algorithms Greedy exploration Independence number Maximum independent sets Random graphs Graph theory Computing the size of maximum independent sets is an NP-hard 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. © is is held held by by author/owner(s). author/owner(s). 2019 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01635999_v46_n3_p27_Bermolen http://hdl.handle.net/20.500.12110/paper_01635999_v46_n3_p27_Bermolen |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Exploration algorithms Independence number Large random graphs Computational complexity Graphic methods Hydrodynamics IEEE Standards 802.11-based wireless networks Asymptotically optimal Degree-greedy algorithm Exploration algorithms Greedy exploration Independence number Maximum independent sets Random graphs Graph theory |
| spellingShingle |
Exploration algorithms Independence number Large random graphs Computational complexity Graphic methods Hydrodynamics IEEE Standards 802.11-based wireless networks Asymptotically optimal Degree-greedy algorithm Exploration algorithms Greedy exploration Independence number Maximum independent sets Random graphs Graph theory Degree-greedy algorithms on large random graphs |
| topic_facet |
Exploration algorithms Independence number Large random graphs Computational complexity Graphic methods Hydrodynamics IEEE Standards 802.11-based wireless networks Asymptotically optimal Degree-greedy algorithm Exploration algorithms Greedy exploration Independence number Maximum independent sets Random graphs Graph theory |
| description |
Computing the size of maximum independent sets is an NP-hard 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. © is is held held by by author/owner(s). author/owner(s). |
| title |
Degree-greedy algorithms on large random graphs |
| title_short |
Degree-greedy algorithms on large random graphs |
| title_full |
Degree-greedy algorithms on large random graphs |
| title_fullStr |
Degree-greedy algorithms on large random graphs |
| title_full_unstemmed |
Degree-greedy algorithms on large random graphs |
| title_sort |
degree-greedy algorithms on large random graphs |
| publishDate |
2019 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01635999_v46_n3_p27_Bermolen http://hdl.handle.net/20.500.12110/paper_01635999_v46_n3_p27_Bermolen |
| _version_ |
1768542358272475136 |