Navegar

Colección

Datos Estadísticas

Conferencia

Bermolen, P.; Jonckheere, M.; Larroca, F.; Saenz, M. "Degree-greedy algorithms on large random graphs" (2019) 36th IFIP Performance Conference 2018. 46(3):27-32
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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).

Registro:

Documento: Conferencia
Título:Degree-greedy algorithms on large random graphs
Autor:Bermolen, P.; Jonckheere, M.; Larroca, F.; Saenz, M.
Filiación:Facultad de Ingeniería, Universidad de la República, Montevideo, Uruguay
Instituto de Cálculo, Universidad de Buenos Aires, Conicet Buenos Aires, Argentina
Instituto de Cálculo, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave: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
Año:2019
Volumen:46
Número:3
Página de inicio:27
Página de fin:32
DOI: http://dx.doi.org/10.1145/3308897.3308910
Título revista:36th IFIP Performance Conference 2018
Título revista abreviado:Perform Eval Rev
ISSN:01635999
CODEN:PERED
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01635999_v46_n3_p27_Bermolen

Referencias:

  • Aronson, J., Frieze, A., Pittel, B.G., Maximum matchings in sparse random graphs: Karp–Sipser revisited (1998) Random Structures & Algorithms, 12 (2), pp. 111-177. , 1998
  • Bermolen, P., Jonckheere, M., Moyal, P., The jamming constant of uniform random graphs (2017) Stochastic Processes and Their Applications, 127 (7), pp. 2138-2178. , 2017
  • Bianchi, G., Performance analysis of the IEEE 802.11 distributed coordination function (2000) IEEE Journal on Selected Areas in Communications, 18 (3), pp. 535-547. , March 2000
  • Brightwell, G., Janson, S., Luczak, M., The Greedy Independent Set in a Random Graph with Given Degrees (2017) Random Structures and Algorithms, 51 (4), pp. 565-586. , 2017
  • Ding, J., Sly, A., Sun, N., Maximum independent sets on random regular graphs (2016) Acta Mathematica, 217 (2), pp. 263-340. , 2016
  • Jonckheere, M., Sáenz, M., (2018) Asymptotic Optimality of Degree-Greedy Discovering of Independent Sets in Configuration Model Graphs, , arXiv preprint 2018
  • Karp, R.M., Sipser, M., Maximum matching in sparse random graphs (1981) Foundations of Computer Science, 1981. SFCS’81. 22nd Annual Symposium on., pp. 364-375. , IEEE
  • Laufer, R., Kleinrock, L., The Capacity of Wireless CSMA/CA Networks (2016) IEEE/ACM Transactions on Networking, 24 (3), pp. 1518-1532. , June 2016
  • Liew, S.C., Kai, C.H., Leung, H.C., Wong, P., Back-of-the-Envelope Computation of Throughput Distributions in CSMA Wireless Networks (2010) IEEE Transactions on Mobile Computing, 9 (9), pp. 1319-1331. , Sept 2010
  • (2018) OpenCellID, , http://opencellid.org/, unwiredlabs
  • Vigoda, E., A note on the Glauber dynamics for sampling independent sets (2001) The Electronic Journal of Combinatorics, 8, p. 1. , 2001
  • Wormald, N.C., Differential equations for random processes and random graphs (1995) The Annals of Applied Probability, pp. 1217-1235. , 1995

Citas:

---------- APA ----------
Bermolen, P., Jonckheere, M., Larroca, F. & Saenz, M. (2019) . Degree-greedy algorithms on large random graphs. 36th IFIP Performance Conference 2018, 46(3), 27-32.
http://dx.doi.org/10.1145/3308897.3308910
---------- CHICAGO ----------
Bermolen, P., Jonckheere, M., Larroca, F., Saenz, M. "Degree-greedy algorithms on large random graphs" . 36th IFIP Performance Conference 2018 46, no. 3 (2019) : 27-32.
http://dx.doi.org/10.1145/3308897.3308910
---------- MLA ----------
Bermolen, P., Jonckheere, M., Larroca, F., Saenz, M. "Degree-greedy algorithms on large random graphs" . 36th IFIP Performance Conference 2018, vol. 46, no. 3, 2019, pp. 27-32.
http://dx.doi.org/10.1145/3308897.3308910
---------- VANCOUVER ----------
Bermolen, P., Jonckheere, M., Larroca, F., Saenz, M. Degree-greedy algorithms on large random graphs. Perform Eval Rev. 2019;46(3):27-32.
http://dx.doi.org/10.1145/3308897.3308910