I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent sets in Random Geometric Graphs.

  • $\begingroup$ For RGGs generally, see Mark Walters: "Random geometric graphs", in Surveys in Combinatorics (LMS lecture series 392), CUP 2011. For independent sets, you can use google scholar as well as me - I found some discussion in an article "On the chromatic number of random geometric graphs", McDiarmid and Muller, 2011. Also, many papers on wireless sensor networks. $\endgroup$ – user25199 Sep 17 '14 at 16:26
  • $\begingroup$ Do you know if i can get an online copy of the Survey Paper by Mark Walters? $\endgroup$ – Pavan Sangha Sep 17 '14 at 19:39
  • $\begingroup$ The link provided at google scholar is nozdr.ru/data/media/biblioteka/kolxo3/M_Mathematics/MA_Algebra/… $\endgroup$ – user25199 Sep 18 '14 at 8:34

Unit disk graphs are a special type of random geometric graphs, where two of the given nodes on a plane share an edge if their Euclidean distance is less or equal to one. This class has been studied quite a lot and it is probably a good starting point for you. I'm not an expert, but here is a list of paper (and references therein) where I would start from (in chronological order).

  • B. N. Clark, C. J. Colbourn, D. S. Johnson, Unit disk graphs (1990)
  • J. Díaz, J. Petit, M. Serna, Random Geometric Problems on $[0, 1]^2$ (1999)
  • T. Nieberg, J. Hurink, W. Kern, A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs (2005)
  • W. Wua, H. Dub, X. Jiab, Y. Lic, S. C.H. Huangb, Minimum connected dominating sets and maximal independent sets in unit disk graphs (2006)
  • C. Mcdiarmid, T. Müller, On the chromatic number of random geometric graphs (2011)
  • D. Mahjoub, D. W. Matula, Experimental Study of Independent and Dominating Sets in Wireless Sensor Networks Using Graph Coloring Algorithms (2009)
  • P. Hu, K. Xing, L. Huang, Y. Wang, D. Wang, P. Li, A Maximal Independent Set Based Giant Component Formation in Random Unit-Disk Graphs (2011)

see C. Mcdiarmid and T. M¨uller, “On the Chromatic Number of Random Geometric Graphs,” Combinatorica, vol. 31, no. 4, pp. 423-488, Nov. 2011

  • $\begingroup$ Thanks! Thats a pretty large document any ideas on where i can find more specific work to independent sets in the paper? $\endgroup$ – Pavan Sangha May 26 '15 at 11:16
  • $\begingroup$ As far as I remember, it was at the very beginning. see Theorem 3 of arxiv.org/abs/1311.5527 $\endgroup$ – Jeff May 26 '15 at 16:39
  • $\begingroup$ Ok thanks, but isn't theorem 3 concerning the chromatic number and not necessarily the independent set? $\endgroup$ – Pavan Sangha May 27 '15 at 9:02
  • $\begingroup$ First of all, there are many independent set, each can be obtained using a proper coloring. The independence number of a graph, that is, the cardinality of the maximum independent set, is unique and has several relationship with the chromatic number, see e.g., planetmath.org/sizeofmaximalindependentsetandchromaticnumber $\endgroup$ – Jeff May 27 '15 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.