3
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2014 at 16:26
  • $\begingroup$ Do you know if i can get an online copy of the Survey Paper by Mark Walters? $\endgroup$ Sep 17, 2014 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, 2014 at 8:34

2 Answers 2

2
$\begingroup$

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)
$\endgroup$
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thanks! Thats a pretty large document any ideas on where i can find more specific work to independent sets in the paper? $\endgroup$ May 26, 2015 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, 2015 at 16:39
  • $\begingroup$ Ok thanks, but isn't theorem 3 concerning the chromatic number and not necessarily the independent set? $\endgroup$ May 27, 2015 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, 2015 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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